Cho một cây gồm $n$ đỉnh, mỗi đỉnh được tô màu xanh lơ (cyan) hoặc màu trắng. Đối với một đường đi đơn trên cây, gọi $c$ là số đỉnh màu xanh lơ và $w$ là số đỉnh màu trắng trên đường đi đó. Giá trị của đường đi là $(c + w) - 2 \times |c - w|$, trong đó $|c - w|$ là giá trị tuyệt đối của $(c - w)$.
Định nghĩa độ sâu của một đỉnh $u$ là số cạnh trên đường đi ngắn nhất từ đỉnh $1$ đến đỉnh $u$. Định nghĩa đỉnh khóa của một đường đi đơn là đỉnh có độ sâu nhỏ nhất trong số tất cả các đỉnh trên đường đi đó. Có thể chứng minh rằng đỉnh khóa của một đường đi đơn là duy nhất.
Với mỗi $1 \le i \le n$, hãy tính giá trị lớn nhất trong số tất cả các đường đi đơn có đỉnh khóa là $i$.
Nhắc lại rằng một đường đi trên cây là một dãy đỉnh khác rỗng $p_1, p_2, \dots, p_k$ sao cho mỗi cặp đỉnh liên tiếp trong dãy được nối với nhau bởi một cạnh. Đường đi đơn là đường đi mà tất cả các đỉnh trên đó đều phân biệt. Một đỉnh đơn lẻ cũng có thể tạo thành một đường đi đơn.
Dữ liệu vào
Có nhiều bộ dữ liệu. Dòng đầu tiên của đầu vào chứa một số nguyên $T$ ($1 \le T \le 10^5$) cho biết số lượng bộ dữ liệu. Đối với mỗi bộ dữ liệu:
Dòng đầu tiên chứa một số nguyên $n$ ($2 \le n \le 4 \times 10^5$) cho biết số lượng đỉnh.
Dòng thứ hai chứa một xâu 01 có độ dài $n$, cho biết màu của từng đỉnh. Nếu ký tự thứ $i$ là 0, đỉnh thứ $i$ được tô màu xanh lơ; ngược lại, đỉnh thứ $i$ được tô màu trắng.
Trong $(n - 1)$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $u_i$ và $v_i$ ($1 \le u_i, v_i \le n$), cho biết một cạnh nối hai đỉnh $u_i$ và $v_i$. Dữ liệu đảm bảo các cạnh đã cho tạo thành một cây.
Dữ liệu đảm bảo tổng của $n$ trong tất cả các bộ dữ liệu không vượt quá $4 \times 10^5$.
Dữ liệu ra
Đối với mỗi bộ dữ liệu, hãy in ra $n$ dòng, mỗi dòng chứa một số nguyên. Dòng thứ $i$ là giá trị lớn nhất trong số tất cả các đường đi đơn có đỉnh khóa là $i$.
Ví dụ
Ghi chú
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