Dato un albero con $n$ vertici, ogni vertice è colorato di ciano oppure di bianco. Per un cammino semplice nell'albero, sia $c$ il numero di vertici ciano e $w$ il numero di vertici bianchi nel cammino. Il valore del cammino è $(c + w) - 2 \times |c - w|$, dove $|c - w|$ è il valore assoluto di $(c - w)$.
Si definisce profondità di un vertice $u$ il numero di archi sul cammino minimo dal vertice $1$ al vertice $u$. Si definisce vertice chiave di un cammino semplice il vertice con profondità minima tra tutti i vertici del cammino. Si può dimostrare che il vertice chiave di un cammino semplice è unico.
Per ogni $1 \le i \le n$, calcola il valore massimo tra tutti i cammini semplici il cui vertice chiave è $i$.
Ricordiamo che un cammino nell'albero è una sequenza non vuota di vertici $p_1, p_2, \dots, p_k$ tale che ogni coppia di vertici adiacenti in questa sequenza sia collegata da un arco. Un cammino semplice è un cammino in cui tutti i vertici sono distinti. Anche un singolo vertice può formare un cammino semplice.
Input
Ci sono più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 10^5$) che indica il numero di casi di test. Per ciascun caso di test:
La prima riga contiene un intero $n$ ($2 \le n \le 4 \times 10^5$) che indica il numero di vertici.
La seconda riga contiene una stringa 01 di lunghezza $n$, che indica il colore di ciascun vertice. Se l'$i$-esimo carattere è 0, l'$i$-esimo vertice è colorato di ciano; altrimenti, l'$i$-esimo vertice è colorato di bianco.
Nelle successive $(n - 1)$ righe, l'$i$-esima riga contiene due interi $u_i$ e $v_i$ ($1 \le u_i, v_i \le n$), che indicano un arco che collega i vertici $u_i$ e $v_i$. È garantito che gli archi forniti formino un albero.
È garantito che la somma di $n$ su tutti i casi di test non superi $4 \times 10^5$.
Output
Per ciascun caso di test stampa $n$ righe, ciascuna contenente un intero. L'$i$-esima riga è il valore massimo tra tutti i cammini semplici il cui vertice chiave è $i$.
Esempi
Note
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