Gegeben ist ein Baum mit $n$ Knoten, wobei jeder Knoten entweder cyan oder weiß gefärbt ist. Für einen einfachen Pfad im Baum sei $c$ die Anzahl der cyanfarbenen Knoten und $w$ die Anzahl der weißen Knoten auf dem Pfad. Der Wert des Pfades beträgt $(c + w) - 2 \times |c - w|$, wobei $|c - w|$ der Absolutbetrag von $(c - w)$ ist.
Die Tiefe eines Knotens $u$ ist definiert als die Anzahl der Kanten auf dem kürzesten Pfad von Knoten $1$ zu Knoten $u$. Der Schlüsselknoten eines einfachen Pfades ist definiert als der Knoten mit der minimalen Tiefe unter allen Knoten auf diesem Pfad. Es lässt sich beweisen, dass der Schlüsselknoten eines einfachen Pfades eindeutig ist.
Berechnen Sie für jedes $1 \le i \le n$ den maximalen Wert unter allen einfachen Pfaden, deren Schlüsselknoten $i$ ist.
Zur Erinnerung: Ein Pfad im Baum ist eine nichtleere Folge von Knoten $p_1, p_2, \dots, p_k$, sodass jedes Paar benachbarter Knoten in dieser Folge durch eine Kante verbunden ist. Ein einfacher Pfad ist ein Pfad, in dem alle Knoten paarweise verschieden sind. Auch ein einzelner Knoten kann einen einfachen Pfad bilden.
Eingabe
Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 10^5$), die die Anzahl der Testfälle angibt. Für jeden Testfall gilt:
Die erste Zeile enthält eine ganze Zahl $n$ ($2 \le n \le 4 \times 10^5$), die die Anzahl der Knoten angibt.
Die zweite Zeile enthält eine 01-Zeichenkette der Länge $n$, die die Farbe jedes Knotens angibt. Ist das $i$-te Zeichen 0, so ist der $i$-te Knoten cyan gefärbt; andernfalls ist der $i$-te Knoten weiß gefärbt.
In den folgenden $(n - 1)$ Zeilen enthält die $i$-te Zeile zwei ganze Zahlen $u_i$ und $v_i$ ($1 \le u_i, v_i \le n$), die eine Kante zwischen den Knoten $u_i$ und $v_i$ angeben. Es wird garantiert, dass die gegebenen Kanten einen Baum bilden.
Es wird garantiert, dass die Summe von $n$ über alle Testfälle $4 \times 10^5$ nicht überschreitet.
Ausgabe
Geben Sie für jeden Testfall $n$ Zeilen aus, die jeweils eine ganze Zahl enthalten. Die $i$-te Zeile ist der maximale Wert unter allen einfachen Pfaden, deren Schlüsselknoten $i$ ist.
Beispiele
Hinweis
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