题目背景

$\texttt{I'm getting tired of hiding.}$

声明：上述图片取自网络，pid:6544352，如有侵权，告知即删。

题目描述

给定一棵 $n$ 个结点的有根树，根结点编号为 $1$。设以 $i$ 为根的子树为 $T_i$。你需要给每个结点赋一个正整数点权 $v_i$，使得所有点的点权恰为 $1,2,\dots,n$ 各一个。记

$$f=\sum_{i=1}^{n}R_i,$$

其中 $R_i$ 是以 $i$ 为根的子树中点权的极差，即

$$R_i=\max_{j \in T_i}\{v_j\}-\min_{j \in T_i}\{v_j\}. $$

对于所有的赋点权的方式，请求出一组使 $f$ 取到最小值的点权。

输入格式

第一行一个正整数 $n$ 表示树的结点数。

接下来 $n-1$ 行，每行两个正整数 $u,v$，表示 $u,v$ 之间有一条边。

输出格式

第一行一个 $1,2,\dots,n$ 的排列，表示结点 $1,2,\dots,n$ 的点权。由于赋点权的方式可能有很多种，你只需要输出其中任意一种即可。

3
1 2
1 3

1 2 3

2
1 2

1 2

5
1 2
2 3
3 4
4 5

1 2 3 4 5

提示

样例说明

输入 $\#1$

$R_1=3-1=2,R_2=2-2=0,R_3=3-3=0,f=R_1+R_2+R_3=2$，可以证明，不存在使得 $f$ 更小的构造。

---

数据范围

对于 $10\%$ 的数据，$n \le 10$；

对于另外 $10\%$ 的数据，树是一条链；

对于另外 $20\%$ 的数据，有一个结点与其他 $n-1$ 个结点都相连；

对于另外 $20\%$ 的数据，树是一棵完全二叉树，即除了叶子结点外每个结点都恰有两个子结点；

对于 $100\%$ 的数据，$1 \le n \le 10^6$。