题号：NC200474
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 100 M，其他语言200 M
64bit IO Format: %lld
题目描述
圣诞节将至，会长为了得到圣诞礼物参加了迷宫抢旗活动。这个迷宫有N个红旗，这N个红旗之间只有N-1条路可以互通，他要都拿到且不走重复路才可以得到奖品。活动人员发放地图给他，现在他在第S个红旗处，他想要拿到第T个红旗，必须先经过的前一个红旗处是第几个？
输入描述:
第一行输入一个整数M表示测试数据共有M(1<=M<=5)组
每组测试数据的第一行输入一个正整数N(1<=N<=100000)和一个正整数S(1<=S<=100000)，N表示红旗的总个数，S表示会长所在红旗处
随后的N-1行，每行有两个正整数a,b(1<=a,b<=N)，表示第a个红旗和第b个红旗之间有一条路连通。
输出描述:
每组测试数据输N个正整数，其中，第i个数表示从S走到i个红旗，必须要经过的上一个红旗的编号。（其中i=S时，请输出-1）
示例1
输入
复制
1
10 1
1 9
1 8
8 10
10 3
8 6
1 2
10 4
9 5
3 7