Description

旅行家Sam要游玩N个城市，这N个城市间只有N-1条路把这个N个城市连接起来。

Sam准备从第S号城市出发，他想知道如果自己要去参观第K号城市，必须经过的前一个城市是几号城市（假设你不走重复的路）。

Input Format

第一行输入一个整数T表示测试数据共有T (1 ≤ T ≤ 5) 组。

每组测试数据的第一行输入一个正整数N (1 ≤ N ≤ 100000) 和一个正整数S (1 ≤ S ≤ 100000)，N表示城市的总个数，S表示起点城市编号。

随后的N-1行，每行有两个正整数a,b (1 ≤ a,b ≤ N)，表示第a号城市和第b号城市之间有一条路连通。

Output Format

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

1
4 1
1 2
1 3
2 4​

-1 1 1 2​

Source

基础百练 搜索 dfs