Hay $N$ ardillas almacenando bellotas en un árbol. El roble (botánico) es también un árbol en la teoría de grafos: un grafo conexo con $N$ vértices etiquetados del $1$ al $N$ y $N - 1$ aristas no dirigidas. Cada ardilla se sitúa en un vértice diferente del árbol y dos ardillas son vecinas si sus vértices comparten una arista.

Paul Danese, CC BY-SA 4.0, vía Wikimedia Commons

En orden ascendente de la etiqueta del vértice, comenzando con la ardilla en el vértice $1$, cada ardilla roba una bellota de la ardilla vecina que actualmente tenga la mayor cantidad de bellotas. Si varias ardillas vecinas están empatadas por tener la mayor cantidad de bellotas, ¡la ardilla roba una bellota de cada una de ellas!

Para limitar las consecuencias de estos altercados, deseas distribuir bellotas a las ardillas de modo que cada ardilla comience con al menos $N$ bellotas (para que ninguna ardilla se quede sin bellotas debido a los robos) y termine con la misma cantidad de bellotas después de que todas las $N$ ardillas hayan terminado de robarse entre sí que las que tenían originalmente. Se puede demostrar que existe tal distribución donde cada ardilla comienza con a lo sumo $2N - 1$ bellotas. Encuentra cualquier distribución que satisfaga estas condiciones.

Entrada

La primera línea de la entrada contiene un entero $N$ ($2 \le N \le 10^5$), el número de vértices (y ardillas).

Cada una de las siguientes $N - 1$ líneas contiene dos enteros separados por espacios $u$ y $v$ ($1 \le u, v \le N, u \neq v$), indicando que existe una arista entre los vértices $u$ y $v$. Existe a lo sumo una arista entre cualquier par de vértices, y las aristas forman un árbol.

Salida

Imprime $N$ enteros separados por espacios $d_1, d_2, \dots, d_N$ que satisfagan $N \le d_i \le 2N - 1$, donde $d_i$ es la cantidad de bellotas que deseas distribuir a la ardilla en el vértice $i$. Tu solución será aceptada si cada ardilla termina con la misma cantidad de bellotas con la que comenzó después de que todos los $N$ robos hayan ocurrido. Se puede probar que siempre existe tal distribución de bellotas.

Ejemplos

Ejemplos 1

5
1 2
1 3
1 4
2 5

6 5 7 7 9

Ejemplos 2

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

14 15 10 9 13 14 14 14