3972: 「LibreOJ β Round #3」绯色 IOI（抵达）
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
> 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$。
样例输入 复制
4
3 1
1 2
4 2样例输出 复制
3 2 4 1提示
输入样例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$|$1\leq n\leq 5\times 10^5$|无|