4038. 猴猴吃苹果

【题目描述】

猴猴最喜欢在树上玩耍，一天猴猴又跳上了一棵树，这棵树有$n$个苹果，每个苹果有一个编号，分别为$1 \sim n$，它们之间由$n-1$个树枝相连，猴猴可以从树枝的一端爬到树枝的另一端，所以猴猴可以从任意一个苹果的位置出发爬到任意猴猴想去的苹果的位置。猴猴开始在编号为$k$的苹果的位置，并且把这个苹果吃了，之后每一天猴猴都要去吃一个苹果，但是树上那么多苹果吃哪个呢？猴猴想到自己去吃苹果时一定会把路上遇到的苹果都吃掉，于是猴猴决定去吃能让自己这天吃的苹果数量最多的那个苹果，如果有多个苹果满足条件，猴猴就会去吃这些中编号最小的苹果，那么猴猴会按照什么顺序吃苹果呢？

【输入格式】

第一行两个数$n$和$k$，分别表示苹果的个数和猴猴开始所在苹果编号。

接下来$n-1$行，每行两个整数$x,y$表示苹果$x$和苹果$y$之间有一根树枝相连。

【输出格式】

若干行，每行一个整数表示猴猴吃苹果的顺序。

【样例1输入】

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

【样例1输出】

3
1
7
4
6

【样例1说明】

第一天在编号为$3$的苹果处，最多吃$3$个苹果，可以去$1$或$7$，去$1$。

第二天在编号为$1$的苹果处，最多吃$2$个苹果，去$7$。

第三天在编号为$7$的苹果处，最多吃$1$个苹果，可以去$4$或$6$，去$4$。

第四天在编号为$4$的苹果处，最多吃$1$个苹果，去$6$。

【样例2输入】

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

【样例2输出】

2
3
5
6
7
8

【样例3输入】

4 3
1 2
1 3
2 4

【样例3输出】

3
4

样例下载

【数据规模与约定】

对于$30\%$的数据：$n\leq 100$。

对于$60\%$的数据：$n\leq 1000$。

对于$100\%$的数据：$n\leq 5\times 10^4,1\leq k\leq n$。