题目描述

$N$ 頂点の木があり、頂点には $1,\ 2,\ \dots,\ N$ と番号が振られています。$i$ 番目 $(1\ \leq\ i\ \leq\ N-1)$ の辺は頂点 $A_i$ と頂点 $B_i$ を結んでいます。

木を見つけた E869120 君は、$N$ 個の頂点それぞれに整数を書き込み、square1001 君を驚かせようとしています。彼を驚かせるためには、頂点 $i$ に書かれた整数を $E_i$ とするとき、次の条件を満たす必要があります。

条件1 $E_i\ \geq\ 1$ $(1\ \leq\ i\ \leq\ N)$ を満たす。
条件2 すべての組 $(i,\ j)$ $(1\ \leq\ i\ <\ j\ \leq\ N)$ について、$|E_i\ -\ E_j|\ \geq\ dist(i,\ j)$ を満たす。
条件3 条件 1・条件 2 を満たす中で、$\max(E_1,\ E_2,\ \dots,\ E_N)$ の値が最小になる。

ただし、$dist(i,\ j)$ は次の値を指します。

• 頂点 $i$ から $j$ への単純パス（同じ頂点を $2$ 度通らない経路）の長さ。
• つまり、単純パスを $q_0\ \to\ q_1\ \to\ q_2\ \to\ \cdots\ \to\ q_L$（$q_0\ =\ i,\ q_L\ =\ j$）とするときの $L$ の値。

square1001 君を驚かせるような整数の書き方を $1$ つ構成してください。

输入格式

入力は以下の形式で標準入力から与えられます。

$N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_{N-1}$ $B_{N-1}$

输出格式

木に書き込む整数 $E_1,\ E_2,\ \cdots,\ E_N$ を順に、空白で区切って $1$ 行で出力してください。

問題文の条件を満たす整数の書き込み方が複数存在する場合は、どれを出力しても正解となります。

$E_1$ $E_2$ $\cdots$ $E_{N}$

题目大意

给定一棵 $n$ 个节点的树，要求构造出一个点权序列 $E$，满足以下三个条件：

1.所有 $E_i\ge 1(1\le i\le n)$。

2.对于任意一组 $(i,j)(1 ≤ i < j ≤ N)$，使 $|E_i-E_j|\ge dist(i,j)$，$dist$ 即树上两点距离。

3.使 $E$ 中的最大值最小。

2
1 2

2 1

4
1 2
1 4
2 3

3 2 1 4

提示

制約

• $2\ \leq\ N\ \leq\ 200000$
• $1\ \leq\ A_i\ <\ B_i\ \leq\ N$
• 与えられるグラフは木である
• 入力はすべて整数

Sample Explanation 1

頂点 $1$ に整数 $2$ を、頂点 $2$ に整数 $1$ を書き込んだ場合、$dist(1,\ 2)\ =\ 1$、$|E_1\ -\ E_2|\ =\ 1$ であるため、問題文中の条件 2 を満たします。 その他の条件もすべて満たすため、この書き込み方は square1001 君を驚かせることができます。 他にも、$(E_1,\ E_2)\ =\ (1,\ 2)$ は正解となります。

Sample Explanation 2

他にも、$(E_1,\ E_2,\ E_3,\ E_4)\ =\ (2,\ 3,\ 4,\ 1)$ は正解となります。