$n$ 個の頂点からなる木が与えられます。各頂点はシアンまたは白のいずれかで塗られています。木上の単純パスについて、パスに含まれるシアンの頂点数を $c$、白の頂点数を $w$ とします。このパスの価値は $(c + w) - 2 \times |c - w|$ です。ここで、$|c - w|$ は $(c - w)$ の絶対値を表します。
頂点 $u$ の深さを、頂点 $1$ から頂点 $u$ への最短パスに含まれる辺の本数として定義します。単純パスのキー頂点を、そのパスに含まれるすべての頂点の中で深さが最小の頂点として定義します。単純パスのキー頂点は一意であることが証明できます。
各 $1 \le i \le n$ について、キー頂点が $i$ であるすべての単純パスの中での価値の最大値を求めてください。
なお、木上のパスとは、非空な頂点列 $p_1, p_2, \dots, p_k$ であって、列内で隣接する任意の 2 頂点が辺で結ばれているものを指します。単純パスとは、含まれる頂点がすべて相異なるパスです。単一の頂点も単純パスをなすことができます。
入力
複数のテストケースが与えられます。入力の 1 行目には、テストケースの個数を表す整数 $T$ ($1 \le T \le 10^5$) が与えられます。各テストケースについて:
1 行目には、頂点の個数を表す整数 $n$ ($2 \le n \le 4 \times 10^5$) が与えられます。
2 行目には、各頂点の色を表す長さ $n$ の 01 文字列が与えられます。$i$ 番目の文字が 0 のとき $i$ 番目の頂点はシアンで塗られており、そうでないとき $i$ 番目の頂点は白で塗られています。
続く $(n - 1)$ 行のうち $i$ 行目には、頂点 $u_i$ と $v_i$ を結ぶ辺を表す 2 つの整数 $u_i$ と $v_i$ ($1 \le u_i, v_i \le n$) が与えられます。与えられる辺が木をなすことが保証されています。
すべてのテストケースにおける $n$ の総和は $4 \times 10^5$ を超えないことが保証されています。
出力
各テストケースについて $n$ 行出力してください。各行には 1 つの整数を出力し、$i$ 行目にはキー頂点が $i$ であるすべての単純パスの中での価値の最大値を出力してください。
入出力例
注記
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