暂无测试数据。

在蒜头君的国度里有 $N$ 个城市，这 $N$ 个城市间只有 $N-1$ 条路把这个 $N$ 个城市连接起来。现在，蒜头君在第 $S$ 号城市，他有张该国地图，他想知道如果自己要去参观第 $T$ 号城市，必须经过的前一个城市是几号城市（假设你不走重复的路）。

输入格式

第一行输入一个整数 $M$ 表示测试数据共有 $M(1 \le M \le 5)$ 组。

每组测试数据的第一行输入一个正整数 $N(1 \le N \le 100000)$ 和一个正整数 $S(1 \le S \le N)$，$N$ 表示城市的总个数，$S$ 表示蒜头君所在城市的编号。

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

输出格式

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

1
10 1
1 9
1 8
8 10
10 3
8 6
1 2
10 4
9 5
3 7

-1 1 10 10 9 8 3 1 1 8