有 $N$ 隻松鼠在樹上儲存橡實。這棵（植物學上的）橡樹同時也是圖論中的樹：一個具有 $N$ 個頂點（編號從 $1$ 到 $N$）與 $N-1$ 條無向邊的連通圖。每隻松鼠坐在樹上不同的頂點，若兩隻松鼠所在的頂點有邊相連，則稱牠們為鄰居。

按照頂點編號由小到大的順序，從位於頂點 $1$ 的松鼠開始，每隻松鼠會從目前擁有最多橡實的鄰居那裡偷走一個橡實。如果有多個鄰居同時擁有最多的橡實，該松鼠會從牠們每位身上各偷走一個橡實！

為了限制這些鬧劇的影響，你想要分配橡實給這些松鼠，使得每隻松鼠最初至少擁有 $N$ 個橡實（這樣就不會因為被偷而耗盡橡實），並且在所有 $N$ 隻松鼠都完成偷竊後，每隻松鼠最終擁有的橡實數量與最初相同。可以證明，一定存在一種分配方式，使得每隻松鼠最初擁有的橡實數量不超過 $2N - 1$。請找出任何一種滿足這些條件的分配方式。

輸入格式

第一行包含一個整數 $N$ ($2 \le N \le 10^5$)，代表頂點（以及松鼠）的數量。

接下來的 $N-1$ 行，每行包含兩個以空白分隔的整數 $u$ 與 $v$ ($1 \le u, v \le N, u \neq v$)，表示頂點 $u$ 與 $v$ 之間存在一條邊。任意兩頂點間至多只有一條邊，且這些邊構成一棵樹。

輸出格式

輸出 $N$ 個以空白分隔的整數 $d_1, d_2, \dots, d_N$，滿足 $N \le d_i \le 2N - 1$，其中 $d_i$ 是你想要分配給位於頂點 $i$ 的松鼠的橡實數量。如果每隻松鼠在所有 $N$ 次偷竊發生後，最終擁有的橡實數量與開始時相同，你的解法就會被接受。可以證明，這樣的橡實分配方式總是存在的。

範例

範例輸入 1

5
1 2
1 3
1 4
2 5

範例輸出 1

6 5 7 7 9

範例輸入 2

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

範例輸出 2

14 15 10 9 13 14 14 14

A squirrel storing an acorn on a tree.