Problem I: Traffic Tree

Problem

それぞれ1からNまでの番号が付いたN個の頂点が、N-1本の無向辺によって繋がれたグラフが与えられる。各頂点について、その頂点からスタートしてすべての頂点を訪れるための最短のステップ数を出力せよ。

ただし、ある頂点から1本の辺をたどって別の頂点に移動することを1ステップとする。

Input

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

N
u1 v1
.
.
.
uN−1 vN−1

1行目に、1つの整数Nが与えられる。
続くN-1行のうちi行目にはi番目の辺の両端の頂点番号を表す整数u_i, v_iが空白区切りで与えられる。

Constraints

• 2 ≤ N ≤ 10⁵
• 1 ≤ u_i,v_i ≤ N (1 ≤ i ≤ N-1)
• u_i ≠ v_i
• 与えられるグラフは連結である

Output

頂点1から頂点Nについてi行目に頂点iからスタートしてすべての頂点を訪れるための最短のステップ数を出力せよ。

Sample Input 1

2
1 2

Sample Output 1

1
1

Sample Input 2

6
1 2
1 3
3 4
3 5
5 6

Sample Output 2

7
6
8
7
7
6

Sample Input2の図

Note

Link

 

---