W drzewie znajduje się $N$ wiewiórek przechowujących żołędzie. Drzewo (botaniczne) dębu jest również drzewem w sensie teorii grafów: spójnym grafem o $N$ wierzchołkach ponumerowanych od $1$ do $N$ oraz $N - 1$ nieskierowanych krawędziach. Każda wiewiórka siedzi w innym wierzchołku drzewa, a dwie wiewiórki są sąsiadami, jeśli ich wierzchołki są połączone krawędzią.

W kolejności rosnącej numerów wierzchołków, zaczynając od wiewiórki w wierzchołku $1$, każda wiewiórka kradnie jeden żołądź od sąsiadującej wiewiórki, która aktualnie posiada najwięcej żołędzi. Jeśli wiele sąsiadujących wiewiórek posiada taką samą, największą liczbę żołędzi, wiewiórka kradnie po jednym żołędziu od każdej z nich!

Aby ograniczyć skutki tych psot, chcesz rozdzielić żołędzie między wiewiórki tak, aby każda z nich zaczynała z co najmniej $N$ żołędziami (dzięki czemu żadna wiewiórka nie zostanie z zerową liczbą żołędzi w wyniku kradzieży) i kończyła z taką samą liczbą żołędzi po zakończeniu kradzieży przez wszystkie $N$ wiewiórek, jaką miała na początku. Można wykazać, że istnieje taki rozkład, w którym każda wiewiórka zaczyna z co najwyżej $2N - 1$ żołędziami. Znajdź dowolny rozkład spełniający te warunki.

Wejście

Pierwsza linia wejścia zawiera liczbę całkowitą $N$ ($2 \le N \le 10^5$), liczbę wierzchołków (i wiewiórek).

Każda z kolejnych $N - 1$ linii zawiera dwie liczby całkowite $u$ oraz $v$ ($1 \le u, v \le N, u \neq v$), wskazujące, że istnieje krawędź między wierzchołkami $u$ oraz $v$. Między dowolną parą wierzchołków istnieje co najwyżej jedna krawędź, a krawędzie tworzą drzewo.

Wyjście

Wypisz $N$ liczb całkowitych $d_1, d_2, \dots, d_N$ oddzielonych spacjami, spełniających warunek $N \le d_i \le 2N - 1$, gdzie $d_i$ to liczba żołędzi, którą chcesz przydzielić wiewiórce w wierzchołku $i$. Twoje rozwiązanie zostanie zaakceptowane, jeśli każda wiewiórka po zakończeniu wszystkich $N$ kradzieży będzie miała taką samą liczbę żołędzi, z jaką zaczynała. Można udowodnić, że taki rozkład żołędzi zawsze istnieje.

Przykład

Wejście

5
1 2
1 3
1 4
2 5

Wyjście

6 5 7 7 9

Wejście

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

Wyjście

14 15 10 9 13 14 14 14