กำหนดต้นไม้ที่มี $n$ จุดยอด โดยแต่ละจุดยอดจะถูกระบายด้วยสีฟ้าอมเขียว (cyan) หรือสีขาว สำหรับวิถีเชิงเดียว (simple path) ในต้นไม้ ให้ $c$ เป็นจำนวนจุดยอดสีฟ้าอมเขียว และ $w$ เป็นจำนวนจุดยอดสีขาวในวิถีนั้น ค่าของวิถีคือ $(c + w) - 2 \times |c - w|$ เมื่อ $|c - w|$ คือค่าสัมบูรณ์ของ $(c - w)$
นิยามความลึกของจุดยอด $u$ คือจำนวนเส้นเชื่อมบนวิถีที่สั้นที่สุดจากจุดยอด $1$ ไปยังจุดยอด $u$ และนิยามจุดยอดสำคัญ (key vertex) ของวิถีเชิงเดียวคือจุดยอดที่มีความลึกน้อยที่สุดในบรรดาจุดยอดทั้งหมดในวิถีนั้น สามารถพิสูจน์ได้ว่าจุดยอดสำคัญของวิถีเชิงเดียวมีเพียงจุดเดียวเสมอ
สำหรับแต่ละ $1 \le i \le n$ จงคำนวณค่าสูงสุดในบรรดาวิถีเชิงเดียวทั้งหมดที่มีจุดยอดสำคัญเป็น $i$
ทบทวนว่าวิถีในต้นไม้คือลำดับของจุดยอดที่ไม่ว่าง $p_1, p_2, \dots, p_k$ ซึ่งจุดยอดแต่ละคู่ที่อยู่ติดกันในลำดับนี้เชื่อมต่อกันด้วยเส้นเชื่อม วิถีเชิงเดียวคือวิถีที่จุดยอดทั้งหมดในวิถีแตกต่างกันทั้งหมด จุดยอดเพียงจุดเดียวก็สามารถเป็นวิถีเชิงเดียวได้เช่นกัน
ข้อมูลนำเข้า
มีหลายกรณีทดสอบ บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 10^5$) แทนจำนวนกรณีทดสอบ สำหรับแต่ละกรณีทดสอบ:
บรรทัดแรกประกอบด้วยจำนวนเต็ม $n$ ($2 \le n \le 4 \times 10^5$) แทนจำนวนจุดยอด
บรรทัดที่สองประกอบด้วยสตริง 01 ความยาว $n$ แทนสีของแต่ละจุดยอด หากอักขระตัวที่ $i$ คือ 0 จุดยอดที่ $i$ จะมีสีฟ้าอมเขียว มิฉะนั้นจุดยอดที่ $i$ จะมีสีขาว
สำหรับ $(n - 1)$ บรรทัดถัดไป บรรทัดที่ $i$ ประกอบด้วยจำนวนเต็มสองจำนวนคือ $u_i$ และ $v_i$ ($1 \le u_i, v_i \le n$) แสดงถึงเส้นเชื่อมที่เชื่อมระหว่างจุดยอด $u_i$ และ $v_i$ รับประกันว่าเส้นเชื่อมที่กำหนดให้ประกอบกันเป็นต้นไม้
รับประกันว่าผลรวมของ $n$ จากทุกกรณีทดสอบไม่เกิน $4 \times 10^5$
ข้อมูลส่งออก
สำหรับแต่ละกรณีทดสอบ ให้แสดงผล $n$ บรรทัด แต่ละบรรทัดประกอบด้วยจำนวนเต็มหนึ่งจำนวน โดยบรรทัดที่ $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