Givet ett träd med $n$ hörn är varje hörn färgat antingen cyan eller vitt. För en enkel väg i trädet, låt $c$ vara antalet cyanfärgade hörn och $w$ vara antalet vita hörn på vägen. Vägens värde är $(c + w) - 2 \times |c - w|$, där $|c - w|$ är absolutbeloppet av $(c - w)$.
Definiera djupet för ett hörn $u$ som antalet kanter på den kortaste vägen från hörn $1$ till hörn $u$. Definiera nyckelhörnet för en enkel väg som hörnet med minst djup bland alla hörn på vägen. Det kan visas att nyckelhörnet för en enkel väg är unikt.
För varje $1 \le i \le n$, beräkna det maximala värdet bland alla enkla vägar vars nyckelhörn är $i$.
Kom ihåg att en väg i trädet är en icke-tom följd av hörn $p_1, p_2, \dots, p_k$ sådan att varje par av intilliggande hörn i följden är förbundna med en kant. En enkel väg är en väg där alla hörn är olika. Ett enskilt hörn kan också utgöra en enkel väg.
Indata
Det finns flera testfall. Den första raden i indatan innehåller ett heltal $T$ ($1 \le T \le 10^5$) som anger antalet testfall. För varje testfall:
Den första raden innehåller ett heltal $n$ ($2 \le n \le 4 \times 10^5$) som anger antalet hörn.
Den andra raden innehåller en 01-sträng av längd $n$, som anger färgen på varje hörn. Om det $i$-te tecknet är 0 är det $i$-te hörnet cyanfärgat; annars är det $i$-te hörnet vitt.
På de följande $(n - 1)$ raderna innehåller den $i$-te raden två heltal $u_i$ och $v_i$ ($1 \le u_i, v_i \le n$), vilket anger en kant som förbinder hörnen $u_i$ och $v_i$. Det garanteras att de givna kanterna bildar ett träd.
Det garanteras att summan av $n$ över alla testfall inte överstiger $4 \times 10^5$.
Utdata
För varje testfall, skriv ut $n$ rader som var och en innehåller ett heltal. Den $i$-te raden är det maximala värdet bland alla enkla vägar vars nyckelhörn är $i$.
Exempel
Notering
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