[AGC029E] Wandering TKHS

## 题目描述 高桥君的公司里有 $n$ 个房间，形成一棵树的结构。某一次他在第 $r$ 个房间里迷路了，他想回到第 $1$ 个房间。为了回到 $1$ 号房间，他会做以下操作： - 设 $S$ 是一些点的集合，一开始令 $S=\{r\}$. - 他会选择 $S$ 之外的，与 $S$ 中的点相连的，编号最小的点 $x$，然后把它加入 $S$ - 若 $1\in S$ 则停止操作，否则重复操作。 设 $c_r=|S|-1$，要求 $c_2,c_3,\dots,c_n$。 ## 数据范围 $n\le 2\times 10^5$

[problemUrl]: https://atcoder.jp/contests/agc029/tasks/agc029_e 高橋君の会社は $ N $ 個の部屋からなり、各部屋には $ 1 $ から $ N $ の番号が割り振られています。 また、$ N-1 $ 本の通路があり、$ i $ 番目の通路は部屋 $ a_i $ と部屋 $ b_i $ を繋いでいます。 どの $ 2 $ つの部屋の間もこれらの通路のみを通って移動できることが分かっています。 今高橋君はある部屋に迷い込んでしまいました。この部屋を $ r $ とします。 そこで、高橋君は自分の部屋である部屋 $ 1 $ に戻るために、以下の方法で移動することを繰り返すことにしました。 - 今まで訪れた部屋に隣接する部屋の中でまだ訪れていない部屋の内、番号が一番小さい部屋に移動する。 部屋 $ 1 $ に戻るまでに行う必要のある移動の回数を $ c_r $ とします。 $ c_2,c_3,...,c_N $ をすべて求めてください。 ただし、$ 1 $ 回の移動でいくつの通路を通るとしても、移動は $ 1 $ 回として数えられることに注意してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ b_1 $ $ : $ $ a_{N-1} $ $ b_{N-1} $

各 $ r $ に対して $ c_r $ を以下の形式に従って出力せよ。 > $ c_2 $ $ c_3 $ $ ... $ $ c_N $

6
1 5
5 6
6 2
6 3
6 4

5 5 5 1 5

6
1 2
2 3
3 4
4 5
5 6

1 2 3 4 5

10
1 5
5 6
6 10
6 4
10 3
10 8
8 2
4 7
4 9

7 5 3 1 3 4 7 4 5

### 制約 - $ 2\ \leq\ N\ \leq\ 2\times\ 10^5 $ - $ 1\ \leq\ a_i,b_i\ \leq\ N $ - $ a_i\ \neq\ b_i $ - 入力で与えられるグラフは木である。 ### Sample Explanation 1 例えば部屋 $ 2 $ に迷い込んでいた場合、高橋君は以下のように移動します。 - 部屋 $ 6 $ に移動する。 - 部屋 $ 3 $ に移動する。 - 部屋 $ 4 $ に移動する。 - 部屋 $ 5 $ に移動する。 - 部屋 $ 1 $ に移動する。