木の上にどんぐりを蓄えている $N$ 匹のリスがいる。この（植物学的な）オークの木は、グラフ理論における木でもある。すなわち、$1$ から $N$ までの番号が付けられた $N$ 個の頂点と $N-1$ 本の無向辺からなる連結グラフである。各リスは木の異なる頂点に座っており、頂点同士が辺で結ばれている場合、その頂点にいるリス同士は「隣人」である。

頂点 $1$ にいるリスから順に、頂点番号の昇順で、各リスは現在最も多くのどんぐりを持っている隣人のリスからどんぐりを $1$ つ盗む。もし最も多くのどんぐりを持っている隣人が複数いる場合、そのリスはそれら全員から $1$ つずつどんぐりを盗む！

この騒動の影響を抑えるために、各リスが最初に少なくとも $N$ 個のどんぐりを持つように（盗難によってどんぐりが尽きることがないように）、かつ $N$ 匹のリス全員が盗み終えた後に、各リスが最初に持っていたどんぐりの数と同じ数になるように、どんぐりを分配したい。すべてのリスが最初に最大で $2N-1$ 個のどんぐりを持つような分配方法が存在することが示されている。これらの条件を満たす分配方法を一つ求めよ。

入力

入力の最初の行には、頂点（およびリス）の数である整数 $N$ ($2 \le N \le 10^5$) が含まれる。

続く $N-1$ 行の各行には、2つの整数 $u$ と $v$ ($1 \le u, v \le N, u \neq v$) が含まれ、頂点 $u$ と $v$ の間に辺が存在することを示している。どの頂点のペア間にも辺は最大で1本であり、これらの辺は木を形成している。

出力

頂点 $i$ にいるリスに分配したいどんぐりの数 $d_i$ を、$N \le d_i \le 2N-1$ を満たすように $N$ 個の整数で空白区切りで出力せよ。すべてのリスが盗みを終えた後、各リスが最初に持っていたどんぐりの数と同じ数になっていれば、その解は正解となる。このようなどんぐりの分配方法は常に存在することが証明されている。

Paul Danese, CC BY-SA 4.0, via Wikimedia Commons

入出力例

入出力例 1

5
1 2
1 3
1 4
2 5

6 5 7 7 9

入出力例 2

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

14 15 10 9 13 14 14 14