Se le proporciona un árbol con raíz compuesto por ~n~ nodos. Los nodos están numerados ~1,2,\ldots,n~, y el nodo ~1~ es la raíz. Cada nodo tiene un color.

Su tarea consiste en determinar, para cada nodo, el número de colores distintos en su subárbol.

Entrada

• La primera línea de entrada contiene un entero ~n~: el número de nodos. Los nodos están numerados ~1,2,\ldots,n~.
• La siguiente línea consta de ~n~ enteros ~c_1,c_2,\ldots,c_n~: el color de cada nodo.
• Luego hay ~n-1~ líneas que describen los arcos. Cada línea contiene dos enteros ~a~ y ~b~: hay un arco entre los nodos ~a~ y ~b~.

Salida

Imprima ~n~ enteros: para cada nodo ~1,2,\ldots,n~, el número de colores distintos.

Restricciones

• ~1 \leq n \leq 2 \cdot 10^5~
• ~1 \leq a,b \leq n~
• ~1 \leq c_i \leq 10^9~

Ejemplo de Entrada

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

Ejemplo de Salida

3 1 2 1 1