Descripcion

Hay ~N~ ciudades en el País OCI, numeradas del ~1~ al ~N~. Las ciudades están conectadas por ~N - 1~ carreteras. La i-ésima carretera (~1 \le i \le N - 1~) conecta las ciudades ~A_i~ y ~B_i~ bidireccionalmente. Desde cualquier ciudad a cualquier ciudad es posible viajar utilizando algunas carreteras.

El país OCI tiene algunos locales especialidades. A cada tipo de local especial se le asigna un número entero entre ~1~ y ~M~ inclusive (algún número entero puede no corresponder a ninguna localidad especial en el País OCI). Cada ciudad produce un tipo de especialidad. La ciudad ~j~ (~1 \le j \le N~) produce la especialidad ~C_j~. Varias ciudades pueden producir el mismo tipo de especialidad.

Definimos la distancia entre dos ciudades como el número mínimo de carreteras necesarias para viajar de una a la otra. Para la ciudad ~x~ (~1 \le x \le N~), decimos que la ciudad ~y~ (~1 \le y \le N~, ~y~ ≠ ~x~) es una ciudad única si para cualquier ciudad ~z~ (~1 \le z \le N~, ~z~ ≠ ~x~, ~z~ ≠ ~y~) la distancia entre las ciudades ~x~ e ~y~ es distinta de la distancia entre las ciudades ~x~ y ~z~.

El oci_cub, ministro de transportes, quiere saber para cada ~j~ (~1 \le j \le N~), el número de tipos de especialidades producidas en las ciudades únicas para la ciudad ~j~.

Tarea

Escribe un programa que, dada la información de las carreteras del País OCI y el tipo de especialidades producidas en cada ciudad, calcule para cada ciudad, el número de tipos de especialidades producidas en las ciudades únicas para ella.

Entrada

Lee los siguientes datos de la entrada estándar.

~N~ ~M~

~A_1~ ~B_1~

...

~A_{N-1}~ ~B_{N-1}~

~C_1~ ... ~C_N~

Salida

Escriba ~N~ líneas en la salida estándar. La j-ésima línea (~1 \le j \le N~) debe contener el número de tipos de especialidades producidas en las ciudades únicas para la ciudad ~j~.

Restricciones

• ~2 \le N \le 200 000~.
• ~1 \le M \le N~
• ~1 \le A_i \le N~ (~1 \le i \le N - 1~), ~1 \le B_i \le N~ (~1 \le i \le N - 1~).
• ~A_i~ ≠ ~B_i~ (~1 \le i \le N - 1~)．
• De cualquier ciudad a cualquier ciudad, es posible viajar utilizando algunas carreteras.
• ~1 \le C_j \le M~ (~1 \le j \le N~).

Subtareas

1. (4 puntos) ~N \le 2 000~.
2. (32 puntos) ~M = 1~.
3. (32 puntos) ~M = N, C j = j (1 \le j \le N)~.
4. (32 puntos) No hay restricciones adicionales.

Ejemplos de entrada y salida

Ejemplo de Entrada #1

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

Ejemplo de Salida #1

2
0
1
1
1

Las ciudades únicas para la ciudad ~1~ son las ciudades ~2~ y ~3~, en las que se producen las especialidades ~2~ y ~1~, por lo que la respuesta es ~2~.

No hay ciudades únicas para la ciudad ~2~, por lo que la respuesta es ~0~.

La ciudad única para la ciudad ~1~ es la ciudad ~1~, en la que se produce la especialidad ~1~, por lo que la respuesta es ~1~.

Las ciudades únicas para la ciudad ~4~ son las ciudades ~1~ y ~3~, en ambas se produce la especialidad ~1~, por lo que la respuesta es ~1~.

Las ciudades únicas para la ciudad ~5~ son las ciudades ~1~ y ~3~, en ambas se produce la especialidad ~1~, por lo que la respuesta es ~1~.

Obsérvese que no existe la especialidad ~3~

Ejemplo de Entrada #2

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

Ejemplo de Salida #2

1
1
1
0
1
1
1

Este ejemplo de entrada satisface las restricciones de la subtarea 2.

Ejemplo de Entrada #3

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

Ejemplo de Salida #3

4
3
4
2
0
2
2
0
3
2

Este ejemplo de entrada satisface las restricciones de la subtarea 3.