La Isla Grande está compuesta por ~n~ ciudades, todas enumeradas con un id único de ~1~ a ~n~. Las ~n~ ciudades están conectadas entre sí por líneas de ferrocarril bidireccionales, de manera tal que siempre puedes ir de una ciudad a cualquier otra usando el Tren. No hay caminos circulares en la Isla Grande (ciclos), en otras palabras, no existe ninguna ciudad de la que se pueda salir y luego entrar usando vías diferentes.

La compañía ferroviaria se ha propuesto hacer una remodelación total de todas sus instalaciones. El tren que va desde la ciudad ~i~ a la ciudad ~j~ es el mismo que va desde la ciudad ~j~ a la ciudad ~i~, sin embargo cada par de ciudades posee un tren único para viajar entre ellas. Luego de que se termina el día los trenes necesitan ser trasladados a un parqueo para su cuidado y mantenimiento, el parqueo para el tren que va de la ciudad ~i~ a la ~j~ se encuentra en la ciudad con el mayor id en el camino entre ~i~ y ~j~. No hay trenes para viajar de una ciudad a sí misma.

Los ingenieros de la Isla Grande necesitan tu ayuda para cumplir esta tarea. Para cada ciudad desde ~1~ hasta ~n~ debes decir cuantos trenes se quedan en ella por la noche, así los ingenieros pueden construir los parqueos correspondientes para ello.

Subtareas

• Subtarea 1 ( 8 puntos): Cada ciudad ~i~ está conectada a la ciudad ~i+1~ para todo ~1 \le i \le n-1~.

• Subtarea 2 (14 puntos): Cada ciudad está conectada a lo sumo con otras dos ciudades y ~2 \le n \le 1000~.

• Subtarea 3 (24 puntos): Cada ciudad está conectada a lo sumo con otras dos ciudades.

• Subtarea 4 (24 puntos): ~2 \le n \le 1000~.

• Subtarea 5 (30 puntos): Sin restricciones adicionales.

Entrada

La primera línea contiene un entero ~n(2 \le n \le 2 \cdot 10^{5})~, la cantidad de ciudades en la Isla Grande.

Las próximas ~n-1~ líneas contendrán dos enteros ~u,v(1\le u,v \le n)~ cada una, indicando que hay una vía de ferrocarril entre la ciudad ~u~ y la ciudad ~v~.

Está garantizado que no hay más de una vía entre dos ciudades, que no hay vías que vayan de una ciudad a sí misma, que siempre podrás llegar de una ciudad a otra usando las diferentes vías entre ciudades y que no hay caminos circulares o ciclos.

Salida

Usted deberá imprimir una línea con ~n~ enteros ~a_1,a_2,a_3,\dots, a_n~ indicando que ~a_i~ trenes pasan la noche en la ciudad ~i~.

Ejemplo 1

Entrada

4
1 2
2 3
3 4

Salida

0 1 2 3

Ejemplo 2

Entrada

6
1 5
5 6
6 4
2 5
5 3

Salida

0 0 0 0 6 9

Ejemplo 3

Entrada

5
1 4
4 3
3 2
2 5

Salida

0 0 1 5 4