题目描述

$N$ 頂点の木 $T$ が与えられます。$i$ 番目の辺は頂点 $A_i$ と $B_i$ を結んでいます。

次の条件をともに満たす $N$ 頂点の根付き木 $R$ を $1$ つ求めてください。

• $1\ \leq\ x\ <\ y\ \leq\ N$ を満たす全ての整数の組 $(x,y)$ に対し次が成り立つ
  • $R$ における頂点 $x,y$ の最小共通祖先が頂点 $z$ であるとき、$T$ において 頂点 $x,y$ を結ぶ単純パス上に頂点 $z$ が存在する
• $R$ において、根以外の全ての頂点 $v$ に対し、$v$ を根とする部分木の頂点数の $2$ 倍は、 $v$ の親を根とする部分木の頂点数以下である

なお、この条件を満たす根付き木は必ず存在することが証明できます。

输入格式

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

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

输出格式

問題文中の条件を満たす根付き木を $R$ とする。$R$ における頂点 $i$ の親を頂点 $p_i$ とする（ただし、$i$ が根のときは $p_i=-1$ と定める）。
$N$ 個の整数 $p_1,\ldots,p_N$ をこの順に空白区切りで出力せよ。

题目大意

平衡的树

给你一棵树 $T$，你要建一棵树 $R$，使其满足以下性质：

• 任意两个点 $x,y$ 在 $R$ 中的最近公共祖先 $z$ 在 $T$ 中都位于 $x,y$ 之间的简单路径上。
• 对于任意一个非根的节点 $v$，以它为根的子树大小的两倍不得超过以它父亲为根的子树大小。

对于每个节点，输出它在 $R$ 中父亲的编号，根节点输出 -1。

4
1 2
2 3
3 4

2 -1 4 2

5
1 2
1 3
1 4
1 5

-1 1 1 1 1

提示

制約

• $1\ \leq\ N\ \leq\ 10^5$
• $1\leq\ A_i,B_i\ \leq\ N$
• 入力は全て整数である
• 与えられるグラフは木である

Sample Explanation 1

例えば、$R$ における頂点 $1,3$ の最小共通祖先は頂点 $2$ であり、$T$ において、頂点 $1,3$ を結ぶ単純パス上に頂点 $2$ が存在します。 また、例えば、$R$ における頂点 $4$ を根とする部分木の頂点数は $2$ であり、その $2$ 倍は、頂点 $2$ を根とする部分木の頂点数 $4$ 以下です。