Il y a $N$ écureuils qui stockent des glands dans un arbre. L'arbre (botanique) est également un arbre au sens de la théorie des graphes : un graphe connexe avec $N$ sommets étiquetés de $1$ à $N$ et $N - 1$ arêtes non orientées. Chaque écureuil se trouve sur un sommet différent de l'arbre et deux écureuils sont voisins si leurs sommets partagent une arête.

Dans l'ordre croissant des étiquettes des sommets, en commençant par l'écureuil au sommet $1$, chaque écureuil vole un gland au voisin qui possède actuellement le plus de glands. Si plusieurs voisins sont à égalité pour le nombre maximal de glands, l'écureuil en vole un à chacun d'entre eux !

Pour limiter les conséquences de ces manigances, vous souhaitez distribuer des glands aux écureuils de sorte que chaque écureuil commence avec au moins $N$ glands (afin qu'aucun écureuil ne se retrouve à court de glands à cause des vols) et termine avec le même nombre de glands après que les $N$ écureuils ont fini de se voler les uns les autres qu'au départ. Il peut être démontré qu'une telle distribution existe où chaque écureuil commence avec au plus $2N - 1$ glands. Trouvez une distribution satisfaisant ces conditions.

Entrée

La première ligne de l'entrée contient un entier $N$ ($2 \le N \le 10^5$), le nombre de sommets (et d'écureuils).

Chacune des $N - 1$ lignes suivantes contient deux entiers séparés par un espace $u$ et $v$ ($1 \le u, v \le N, u \neq v$), indiquant qu'une arête existe entre les sommets $u$ et $v$. Il y a au plus une arête entre toute paire de sommets, et les arêtes forment un arbre.

Sortie

Affichez $N$ entiers séparés par des espaces $d_1, d_2, \dots, d_N$ satisfaisant $N \le d_i \le 2N - 1$, où $d_i$ est le nombre de glands que vous souhaitez distribuer à l'écureuil au sommet $i$. Votre solution sera acceptée si chaque écureuil termine avec le même nombre de glands qu'au départ après que les $N$ vols ont eu lieu. Il peut être prouvé qu'une telle distribution de glands existe toujours.

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

Exemples

Exemples 1

5
1 2
1 3
1 4
2 5

6 5 7 7 9

Exemples 2

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

14 15 10 9 13 14 14 14