Descripción

Cada día cada una de las ~N (1 <= N <= 100,000)~ vacas convenientemente numeradas ~1..N~ se mueven desde el establo a su pastizal privado. Los pastizales están organizados como un árbol, con el establo en el pastizal

1. Exactamente ~N-1~ caminos unidireccionales de vacas conectan los pastizales; los pastizales directamente conectados tienen exactamente un camino. El camino ~i~ conecta a los pastizales ~A_i y B_i (1 <= A_i <= N; 1 <= B_i <= N)~.

La vaca i tiene un pastizal privado ~P_i (1 <= P_i <= N)~. La pequeña puerta del establo permite que una sola vaca salga al tiempo; y las pacientes vacas esperan hasta que su vaca predecesora llegue a su pastizal privado. Primero la vaca 1 sale y se mueve al pastizal ~P_1~. Luego la vaca 2 sale y va al pastizal ~P_2~, y así sucesivamente.

Cuando la vaca i va a ~P_i~ ella podría o no podría pasar a través de un pastizal que ya tiene una vaca comiendo. Cuando una vaca está presente en un pastizal, la vaca i camina más despacio de lo usual para prevenir molestar a su amiga.

Considere la siguiente red de pastizales, donde cada número entre paréntesis indica la dueña del pastizal.

Primero, la vaca 1 camina a su pastizal:

Cuando la vaca 2 se mueve a su pastizal, ella primero pasa al pastizal de establo, el pastizal 1. Luego ella pasa a hurtadillas cerca de la vaca 1 en el pastizal 4 antes de llegar a su propio pastizal

La Vaca 3 no va tan lejos – ella se establece en el pastizal de establo, el #1.

La Vaca 4 debe demorarse en el pastizal 1 y en el 4 en su camino al pastizal 5:

La vaca 5 se demora por la vaca 3 en el pastizal 3 y luego entra en su propio pastizal privado:

A GJ le gustaría saber cuantas veces cada vaca tuvo que caminar mas despacio.

Entrada

• Línea 1: La línea 1 contiene un sólo entero: ~N~

• Líneas ~2..N~: La línea ~i+1~ contiene dos enteros separados por espacios: ~A_i y B_i~

• Líneas ~N+1..N+N~: la línea ~N+i~ contiene un solo entero: ~P_i~

Salida

• Lìneas ~1..N~: La línea i contiene el número de veces que la vaca ~i~ tiene que disminuir su velocidad.

Ejemplo de Entrada

5
1 4
5 4
1 3
2 4
4
2
1
5
3

Ejemplo de Salida

0
1
0
2
1