I - Saludos II

Time limit: 2 s
Memory limit: 256 MiB
Languages: C, C++, Java, Haskell, ... (details)

Fito y sus amigos juegan a un extraño juego: Todos se reunen fuera de la casa de Fito, y se forman en una fila. El primero en la fila sale hacia su casa, mientras el segundo espera, una vez el primero termina su viaje es el segundo quien sale, mientras el tercero espera, y así siguen hasta que todos estén en su casa. Es importante saber que la ciudad consiste de $N$ casas (una para cada amigo) conectadas por calles, de forma tal que existe exactamente un camino entre cada par de casas (que no pase dos veces por ninguna casa), y los amigos de Fito siempre tomarán el camino más corto hacia su casa. Cada vez que alguien pasa por una casa donde haya uno de sus amigos lo saludará, para después continuar con su viaje (solo se saludará a Fito si ya le tocó su turno y está dentro de su casa). Fito, siendo muy curioso, quiere saber cuántas veces parará cada amigo a saludar en su viaje, ayúdalo con su problema.

Input

La primera línea contiene $N$, el número de amigos y casas en la ciudad (Fito incluido)
Las siguientes $N - 1$ líneas contendrán $2$ enteros $A$ y $B$ separadas por espacio indicando que hay una carretera bidireccional entre las casas de los amigos $A$ y $B$.
- Para el primer subproblema $(1 \leq N \leq 10000)$  
- Para el segundo subproblema $(1 \leq N \leq 100000)$

La siguientes líneas tendrán $N$ enteros que representan a los amigos (Fito se representa con el número $1$).

Output

$N$ líneas, la $i$-ésima línea contendrá un único entero reflejando la cantidad total de saludos efectuados por el $i$-ésimo amigo.

Sample test(s)

Input
5 1 4 5 4 1 3 2 4 4 2 1 5 3
Output
0 1 0 2 1