题目描述

一棵有 $N$ 个结点的树，树上结点编号为 $1 \sim N$。

指定结点 $R$ 为树的根，并给出树上所有的边，请依次输出结点 $1 \sim N$ 中，除了根以外，每个结点的父元素。

输入格式

第 $1$ 行读入两个整数 $N$ 和 $R$，代表树上结点的数量，及根结点的编号。

接下来 $N-1$ 行，每行读入两个整数 $X,Y$，代表结点 $X,Y$ 之间有一条无向边。

输出格式

输出一行 $N-1$ 个整数，用空格隔开，分别代表结点 $1$ 到 结点 $N$ 中，除了根结点以外的每个结点的父元素的编号。

样例输入 #1

7 7
7 6
5 7
3 2
3 7
4 5
7 1

样例输出 #1

7 3 7 5 7 7

样例输入 #2

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

样例输出 #2

10 9 6 9 9 1 2 1 1

数据范围

数据范围

对于 $30\%$ 的数，$5 \le N \le 100$；

对于 $70\%$ 的数，$5 \le N \le 1000$；

对于 $100\%$ 的数，$5 \le N \le 10^5$，$X,Y$ 均在 $[1,N]$ 的范围内，且题目保证给定的数据能够正确的构成一棵树。