Dane jest drzewo o $n$ wierzchołkach, w którym każdy wierzchołek jest pokolorowany na kolor cyjanowy lub biały. Dla ścieżki prostej w drzewie niech $c$ oznacza liczbę wierzchołków cyjanowych, a $w$ liczbę wierzchołków białych na tej ścieżce. Wartość ścieżki wynosi $(c + w) - 2 \times |c - w|$, gdzie $|c - w|$ oznacza wartość bezwzględną z $(c - w)$.
Zdefiniujmy głębokość wierzchołka $u$ jako liczbę krawędzi na najkrótszej ścieżce z wierzchołka $1$ do wierzchołka $u$. Zdefiniujmy wierzchołek kluczowy ścieżki prostej jako wierzchołek o minimalnej głębokości spośród wszystkich wierzchołków na tej ścieżce. Można udowodnić, że wierzchołek kluczowy dla ścieżki prostej jest wyznaczony jednoznacznie.
Dla każdego $1 \le i \le n$ oblicz maksymalną wartość spośród wszystkich ścieżek prostych, których wierzchołkiem kluczowym jest $i$.
Przypomnijmy, że ścieżką w drzewie nazywamy niepusty ciąg wierzchołków $p_1, p_2, \dots, p_k$ taki, że każda para sąsiednich wierzchołków w tym ciągu jest połączona krawędzią. Ścieżka prosta to ścieżka, w której wszystkie wierzchołki są parami różne. Pojedynczy wierzchołek również może tworzyć ścieżkę prostą.
Wejście
W danych wejściowych znajduje się wiele przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 10^5$) oznaczającą liczbę przypadków testowych. Dla każdego przypadku testowego:
Pierwszy wiersz zawiera liczbę całkowitą $n$ ($2 \le n \le 4 \times 10^5$) oznaczającą liczbę wierzchołków.
Drugi wiersz zawiera napis 01 o długości $n$, określający kolor każdego wierzchołka. Jeśli $i$-ty znak to 0, to $i$-ty wierzchołek jest pokolorowany na cyjanowo; w przeciwnym razie $i$-ty wierzchołek jest pokolorowany na biało.
W kolejnych $(n - 1)$ wierszach $i$-ty wiersz zawiera dwie liczby całkowite $u_i$ oraz $v_i$ ($1 \le u_i, v_i \le n$), oznaczające krawędź łączącą wierzchołki $u_i$ oraz $v_i$. Gwarantuje się, że podane krawędzie tworzą drzewo.
Gwarantuje się, że suma $n$ po wszystkich przypadkach testowych nie przekracza $4 \times 10^5$.
Wyjście
Dla każdego przypadku testowego wypisz $n$ wierszy, z których każdy zawiera jedną liczbę całkowitą. W $i$-tym wierszu powinna znaleźć się maksymalna wartość spośród wszystkich ścieżek prostych, których wierzchołkiem kluczowym jest $i$.
Przykład
Uwagi
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