Gefið er tré með $n$ hnútum þar sem hver hnútur er litaður annaðhvort blágrænn (cyan) eða hvítur. Fyrir einfaldan veg í trénu, látum $c$ vera fjölda blágrænna hnúta og $w$ vera fjölda hvítra hnúta á veginum. Gildi vegarins er $(c + w) - 2 \times |c - w|$, þar sem $|c - w|$ er algildi $(c - w)$.
Skilgreinum dýpt hnúts $u$ sem fjölda leggja á stysta veginum frá hnúti $1$ til hnúts $u$. Skilgreinum lykilhnút einfalds vegar sem hnútinn með minnsta dýpt meðal allra hnúta á veginum. Sanna má að lykilhnútur einfalds vegar er ótvírætt ákvarðaður.
Fyrir hvert $1 \le i \le n$ skal reikna hæsta gildið meðal allra einfaldra vega sem hafa $i$ sem lykilhnút.
Minnist þess að vegur í tré er ekki tóm runa hnúta $p_1, p_2, \dots, p_k$ þannig að sérhvert par aðliggjandi hnúta í rununni er tengt með legg. Einfaldur vegur er vegur þar sem allir hnútar eru ólíkir. Einn stakur hnútur getur einnig myndað einfaldan veg.
Inntak
Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur heiltölu $T$ ($1 \le T \le 10^5$) sem gefur til kynna fjölda prófunartilvika. Fyrir hvert prófunartilvik:
Fyrsta línan inniheldur heiltölu $n$ ($2 \le n \le 4 \times 10^5$) sem gefur til kynna fjölda hnúta.
Önnur línan inniheldur 01-streng af lengd $n$, sem gefur til kynna lit hvers hnúts. Ef $i$-ti stafurinn er 0, þá er $i$-ti hnúturinn blágrænn; annars er $i$-ti hnúturinn hvítur.
Í næstu $(n - 1)$ línum inniheldur $i$-ta línan tvær heiltölur $u_i$ og $v_i$ ($1 \le u_i, v_i \le n$), sem táknar legg sem tengir hnútana $u_i$ og $v_i$. Tryggt er að gefnu leggirnir myndi tré.
Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $4 \times 10^5$.
Úttak
Fyrir hvert prófunartilvik skal skrifa út $n$ línur, þar sem hver lína inniheldur eina heiltölu. $i$-ta línan er hæsta gildið meðal allra einfaldra vega sem hafa $i$ sem lykilhnút.
Dæmi
Athugasemd
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