2869 - 小卖部

题目描述

幸福村的 N 栋房子(房子编号为 1 \sim N)之间通过 N-1 条道路连接,形成了一棵树。

王老板在编号为 T 的房子里开了一家小卖部,请编程求出,从小卖部出发走到离小卖部最远的房子,要经过几栋房子(包含小卖部);并求出哪些编号的房子离小卖部最远?

输入

1 行读入两个整数 NT,代表房子的数量,及开小卖部房子编号。

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

输出

1 行输出从小卖部出发,走到离小卖部最远的房子,经过房子的数量(包含小卖部)。

2 行按照从小到大的顺序,输出离小卖部最远房子的编号,用空格隔开。

样例

输入

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

输出

3
1 2 3 4

输入

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

输出

3
2 6
说明

数据范围

对于 30\% 的数,5 \le N \le 100

对于 70\% 的数,5 \le N \le 1000

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

来源

东方博宜OJ

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 98
通过人数 73
金币数量 1 枚
难度 入门


上一题 下一题