#521. 「LibreOJ β Round #3」绯色 IOI(抵达)

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: liu_cheng_ao

题目描述

Jsp 很快解决了问题,Rlc 正要说什么,却见 Jsp 望向窗外。Rlc 心中一阵失落,顿时没了心情,低下头去默默流着眼泪。

不知过了多久, Rlc 被列车员的通报惊醒:「各位乘客,前方列车即将到达 Oli 国的首都 IlO 市。」Oli 国并不是 Jsp 和 Rlc 的目的地,不过这也让 Rlc 终于抓到了机会。

「Oli 国到了。」
「是啊 …… Oli 国 ……」
「据说曾经被评为地球上最和谐的国家之一呢,Jsp。」
「看起来和这个词没有任何关系?」
「是啊 …… 自从那次之后 ……」
「和你我又有什么关系呢?」
「也许吧。看着我,Jsp。」
「Rlc?」
「这三年你都做了什么呢?」
「OI。」
「接下来的两年呢?」
「……」

二人相对无言,直到列车到达终点。

OIi 国由 n 个城市构成,从 1 n 编号,这 n 个城市由 n-1 条双向道路连通着。
其中每个城市的危险程度不同,城市按危险度从小到大排列为 a_1,a_2,...,a_n
城市太过危险,所以每个城市需要有一个庇护所。定义每个城市的庇护所为与它相连(不包括自身)的危险度最小的城市,出于某种神秘的原因,任意两个不同的城市庇护所不同

可惜,中央政府领导人 *****1317 忘了每个城市的危险度大小,也忘了每个城市庇护所的编号,只记得这些道路。
a_1,a_2,...,a_n 可能有多种取值,但 *****1317 只关心其中字典序最小的。他想要让你给出字典序最小的合法的 a_1,a_2,...,a_n 的取值。

输入格式

第一行一个正整数 n ,表示城市的个数。
接下来 n-1 行,每行两个正整数 u,v ,表示有一条连接 u,v 的双向道路( 1\leq u,v\leq n,u\neq v )。

输出格式

如果合法的 a_1,a_2,...,a_n 不存在,那么输出 -1
否则输出字典序最小的合法的 a_1,a_2,...,a_n

样例

样例输入 1

4
3 1
1 2
4 2

样例输出 1

3 2 4 1

样例解释 1

容易验证,当城市按危险度从小到大排列为 3,2,4,1 ,即各个城市的危险程度从小到大的排名分别为 4,2,1,3 时 1 号城市与 2 号,3 号城市相连,因此 1 号城市的庇护所为 3 号城市。 同样的 2 号城市的庇护所为 4 号城市, 3 号城市的庇护所为1号城市,4 号城市的庇护所为 2 号城市。这时候就满足任意两个不同城市的庇护所不同。

样例输入 2

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

样例输出 2

2 1 3 5 6 9 7 10 4 8 

数据范围与提示

对于所有数据, 1\leq n\leq 5\times 10^5

Subtask # 分值 n 特殊限制
1 15 1\leq n\leq 10
2 30 1\leq n\leq 2000
3 10 1\leq n\leq 5\times 10^5 每条道路满足 v-u=1
4 45