Gitt et tre med $n$ noder, der hver node er farget enten cyan eller hvit. For en enkel sti i treet, la $c$ være antallet cyanfargede noder og $w$ være antallet hvite noder på stien. Verdien til stien er $(c + w) - 2 \times |c - w|$, der $|c - w|$ er absoluttverdien av $(c - w)$.
Definer dybden til en node $u$ som antallet kanter på den korteste stien fra node $1$ til node $u$. Definer nøkkelnoden til en enkel sti som noden med minst dybde blant alle nodene på stien. Det kan bevises at nøkkelnoden for en enkel sti er unik.
For hver $1 \le i \le n$, beregn den maksimale verdien blant alle enkle stier som har $i$ som nøkkelnode.
Husk at en sti i treet er en ikke-tom sekvens av noder $p_1, p_2, \dots, p_k$ slik at hvert par av nabonoder i sekvensen er forbundet med en kant. En enkel sti er en sti der alle nodene er forskjellige. En enkelt node kan også utgjøre en enkel sti.
Inndata
Det er flere testtilfeller. Den første linjen av inndataen inneholder et heltall $T$ ($1 \le T \le 10^5$) som angir antallet testtilfeller. For hvert testtilfelle:
Den første linjen inneholder et heltall $n$ ($2 \le n \le 4 \times 10^5$) som angir antallet noder.
Den andre linjen inneholder en 01-streng med lengde $n$, som angir fargen til hver node. Hvis det $i$-te tegnet er 0, er den $i$-te noden farget cyan; ellers er den $i$-te noden farget hvit.
I de følgende $(n - 1)$ linjene inneholder den $i$-te linjen to heltall $u_i$ og $v_i$ ($1 \le u_i, v_i \le n$), som angir en kant som forbinder nodene $u_i$ og $v_i$. Det er garantert at de oppgitte kantene danner et tre.
Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $4 \times 10^5$.
Utdata
For hvert testtilfelle skal du skrive ut $n$ linjer, der hver linje inneholder ett heltall. Den $i$-te linjen er den maksimale verdien blant alle enkle stier som har $i$ som nøkkelnode.
Eksempler
Merk
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