Dado un árbol con $n$ vértices, cada vértice está coloreado de cian o de blanco. Para un camino simple en el árbol, sea $c$ el número de vértices de color cian y $w$ el número de vértices blancos en el camino. El valor del camino es $(c + w) - 2 \times |c - w|$, donde $|c - w|$ es el valor absoluto de $(c - w)$.
Se define la profundidad de un vértice $u$ como el número de aristas en el camino más corto desde el vértice $1$ hasta el vértice $u$. Se define el vértice clave de un camino simple como el vértice con la menor profundidad entre todos los vértices del camino. Se puede demostrar que el vértice clave de un camino simple es único.
Para cada $1 \le i \le n$, calcula el valor máximo entre todos los caminos simples cuyo vértice clave es $i$.
Recuerda que un camino en el árbol es una secuencia no vacía de vértices $p_1, p_2, \dots, p_k$ tal que cada par de vértices adyacentes en esta secuencia está conectado por una arista. Un camino simple es un camino en el que todos sus vértices son distintos. Un solo vértice también puede formar un camino simple.
Entrada
Hay múltiples casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 10^5$) que indica el número de casos de prueba. Para cada caso de prueba:
La primera línea contiene un entero $n$ ($2 \le n \le 4 \times 10^5$) que indica el número de vértices.
La segunda línea contiene una cadena 01 de longitud $n$, que indica el color de cada vértice. Si el $i$-ésimo carácter es 0, el $i$-ésimo vértice es de color cian; en caso contrario, el $i$-ésimo vértice es de color blanco.
En las siguientes $(n - 1)$ líneas, la $i$-ésima línea contiene dos enteros $u_i$ y $v_i$ ($1 \le u_i, v_i \le n$), que indican una arista que conecta los vértices $u_i$ y $v_i$. Se garantiza que las aristas dadas forman un árbol.
Se garantiza que la suma de $n$ en todos los casos de prueba no supera $4 \times 10^5$.
Salida
Para cada caso de prueba, imprime $n$ líneas, cada una con un entero. La $i$-ésima línea es el valor máximo entre todos los caminos simples cuyo vértice clave es $i$.
Ejemplos
Nota
3
8
00101110
1 2
1 3
3 4
3 5
5 6
5 7
7 8
2
01
1 2
2
00
1 2
6
-1
3
-1
1
-1
2
-1
2
-1
-1
-1