问题1711--漂洋过海来看你

1711: 漂洋过海来看你

时间限制: 1 Sec  内存限制: 128 MB
提交: 134  解决: 45
[状态] [讨论版] [提交] [命题人:]
题目描述

BMan和hyx住在一个神奇的国度,这个国度有N个城市,这N个城市间只有N-1条路把这个N个城市连接起来。 现在BMan在第S号城市,他经常想起那个一起AC过的队友hyx,记忆它总是慢慢的累积,在他心中无法抹去,可是他并不知道hyx 在哪个城市,所以他决定用尽半年的积蓄漂洋过海去找hyx,现在BMan很想知道如果他想去hyx所在的第X号城市,必须经过的前 一个城市是第几号城市(放心,由于心系队友,BMan是不会选择走重复的路的~)

输入

第一行输入一个整数T表示测试数据共有T(1<=T<=10)组 每组测试数据的第一行输入一个正整数N(1<=N<=1000)和一个正整数S(1<=S<=1000),N表示城市的总数,S是BMan所在城市的编号 随后的N-1行,每行有两个正整数a,b(1<=a,b<=N),表示第a号城市和第b号城市之间有一条路连通。

输出

每组测试数据输N个正整数,其中,第i个数表示从S走到i号城市,必须要经过的上一个城市的编号(其中i=S时,请输出-1)

样例输入 Copy
1
10 1
1 9
1 8
8 10
10 3
8 6
1 2
10 4
9 5
3 7
样例输出 Copy
-1 1 10 10 9 8 3 1 1 8