問題文

株式会社 KYOPRO-MASTER には N\ (\leq 100000) 人の社員がおり、1 から N までの番号が付けられています。 ライバル会社に勤務している太郎君は、以下の N-1 個の情報を入手しました。

i 個目の情報: 社員 A_i と社員 B_i は直属の上司と部下の関係にある。ここで、社員 A_i と B_i のどちらが上司かは分かっていない。

社員 T が社長であり、それ以外の N-1 人全員が誰か 1 人の直属の部下であるとき、各社員の「階級」を求めるプログラムを作成してください。 ただし、部下がいない社員の階級は 0 であり、部下がいる社員の階級は、直属の部下における階級の最大値に 1 を足した値であるとします。

制約

• 2 \leq N \leq 100000
• 1 \leq T \leq N
• 1 \leq A_i \lt B_i \leq N\ (1\leq i\leq N-1)
• i \neq j \implies (A_i,B_i) \neq (A_j,B_j)
• 与えられる条件をすべて満たすような直属の上司と部下の関係が存在する。
• 入力は全て整数

入力例 1

7 1
1 2
1 3
3 4
2 5
4 6
4 7

出力例 1

3 1 2 1 0 0 0

入力例 2

15 1
1 2
2 3
1 4
1 5
1 6
6 7
2 8
6 9
9 10
10 11
6 12
12 13
13 14
12 15

出力例 2

4 1 0 0 0 3 0 0 2 1 0 2 1 0 0

与えられるグラフは次のようになります。