#476. 旅游规划

旅游规划

题目描述

W 市的交通规划出现了重大问题,市政府下定决心在全市各大交通路口安排疏导员来疏导密集的车流。但由于人员不足,W 市市长决定只在最需要安排人员的路口安排人员。

具体来说,W 市的交通网络十分简单,由n\red{ n }个交叉路口和n1\red{ n-1 }条街道构成,交叉路口路口编号依次为 0,1,,n1\red{0,1,\cdots ,n-1} 。任意一条街道连接两个交叉路口,且任意两个交叉路口间都存在一条路径互相连接。

经过长期调查,结果显示,如果一个交叉路口位于 W 市交通网最长路径上,那么这个路口必定拥挤不堪。所谓最长路径,定义为某条路径 p=(v1,v2,v3,,vk)\red{p=(v_1,v_2,v_3,\cdots,v_k)},路径经过的路口各不相同,且城市中不存在长度大于k\red{ k }的路径,因此最长路径可能不唯一。因此 W 市市长想知道哪些路口位于城市交通网的最长路径上。

输入格式

第一行一个整数n\red{ n}

之后 n1\red{n-1} 行每行两个整数u,v\red{ u,v},表示u\red{ u }v\red{ v }的路口间存在着一条街道。

输出格式

输出包括若干行,每行包括一个整数——某个位于最长路径上的路口编号。为了确保解唯一,请将所有最长路径上的路口编号按编号顺序由小到大依次输出。

样例

输入样例

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

输出样例

0
1
2
3
4
5
6
8
9

提示

对于全部数据,1n2×105\red{1\le n\le 2\times 10^5}