On vous donne un arbre à $n$ sommets, dont chaque sommet est coloré soit en cyan, soit en blanc. Pour un chemin simple dans l'arbre, soient $c$ le nombre de sommets cyan et $w$ le nombre de sommets blancs sur ce chemin. La valeur du chemin est $(c + w) - 2 \times |c - w|$, où $|c - w|$ désigne la valeur absolue de $(c - w)$.
On définit la profondeur d'un sommet $u$ comme le nombre d'arêtes sur le plus court chemin entre le sommet $1$ et le sommet $u$. On définit le sommet clé d'un chemin simple comme étant le sommet de profondeur minimale parmi tous les sommets du chemin. On peut prouver que le sommet clé d'un chemin simple est unique.
Pour chaque $1 \le i \le n$, calculez la valeur maximale parmi tous les chemins simples dont le sommet clé est $i$.
Rappelons qu'un chemin dans l'arbre est une suite non vide de sommets $p_1, p_2, \dots, p_k$ telle que deux sommets consécutifs de cette suite soient toujours reliés par une arête. Un chemin simple est un chemin dont tous les sommets sont distincts. Un sommet seul peut également former un chemin simple.
Entrée
Il y a plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 10^5$) indiquant le nombre de cas de test. Pour chaque cas de test :
La première ligne contient un entier $n$ ($2 \le n \le 4 \times 10^5$) indiquant le nombre de sommets.
La deuxième ligne contient une chaîne 01 de longueur $n$, indiquant la couleur de chaque sommet. Si le $i$-ème caractère est 0, le $i$-ème sommet est coloré en cyan ; sinon, le $i$-ème sommet est coloré en blanc.
Pour les $(n - 1)$ lignes suivantes, la $i$-ème ligne contient deux entiers $u_i$ et $v_i$ ($1 \le u_i, v_i \le n$), indiquant une arête reliant les sommets $u_i$ et $v_i$. Il est garanti que les arêtes données forment un arbre.
Il est garanti que la somme des $n$ sur l'ensemble des cas de test ne dépasse pas $4 \times 10^5$.
Sortie
Pour chaque cas de test, affichez $n$ lignes contenant chacune un entier. La $i$-ème ligne doit contenir la valeur maximale parmi tous les chemins simples dont le sommet clé est $i$.
Exemples
Remarque
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