เบื้องหน้า Yuki มีทางม้าลายที่แปลกประหลาด

ทางม้าลายนี้มองได้ว่าเป็นต้นไม้ที่มี $n$ จุดยอด โดยเส้นเชื่อมที่ $i$ เชื่อมจุดยอด $u_i$ กับจุดยอด $v_i$ แต่ละจุดยอดถูกระบายเป็นสีดำหรือสีขาว ซึ่งอธิบายด้วยสตริงฐานสอง $s$ ความยาว $n$:

• ถ้า $s_i=0$ จุดยอด $i$ มีสีดำ

• ถ้า $s_i=1$ จุดยอด $i$ มีสีขาว

Yuki มีความสามารถในการกระโดดเท่ากับ $k$ ซึ่งหมายความว่าเมื่อเธออยู่ที่จุดยอด $x$ เธอสามารถกระโดดไปยังจุดยอด $y$ ใดก็ได้ที่ $\operatorname{dist}(x,y)\le k$ โดย $\operatorname{dist}(x,y)$ คือจำนวนเส้นเชื่อมบนวิถีอย่างง่ายระหว่างจุดยอด $x$ กับจุดยอด $y$

ต่อไป Yuki จะกระโดดบนทางม้าลายทั้งหมด $n-1$ รอบ ในรอบที่ $i$ เธอเริ่มที่จุดยอด $1$ และต้องการไปถึงจุดยอด $i+1$ ด้วยการกระโดดเป็นลำดับ ขณะเดียวกัน เธอต้องการให้จำนวนครั้งที่ลงบนจุดยอดสีดำหลังการกระโดดน้อยที่สุด

คุณต้องช่วย Yuki หาจำนวนครั้งน้อยที่สุดที่เธอลงบนจุดยอดสีดำในแต่ละรอบของการกระโดด

ข้อมูลนำเข้า

โจทย์นี้มีหลายกรณีทดสอบ

บรรทัดแรกมีจำนวนเต็มบวก $t$ ($1\le t\le 10^5$) แทนจำนวนกรณีทดสอบ

สำหรับแต่ละกรณีทดสอบ:

• บรรทัดแรกมีจำนวนเต็มบวกสองจำนวน $n,k$ ($1\le n\le 5\cdot 10^5$, $1\le k\le n$)

• บรรทัดที่สองมีสตริงฐานสอง $s$ ความยาว $n$ ($s_i\in\{0,1\}$)

• แต่ละบรรทัดใน $n-1$ บรรทัดถัดไปมีจำนวนเต็มบวกสองจำนวน $u_i,v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$)

รับประกันว่าผลรวมของ $n$ ในทุกกรณีทดสอบไม่เกิน $5\cdot 10^5$

ข้อมูลส่งออก

สำหรับแต่ละกรณีทดสอบ แสดงผลหนึ่งบรรทัดประกอบด้วยจำนวนเต็ม $n-1$ จำนวน โดยจำนวนที่ $i$ แทนจำนวนครั้งน้อยที่สุดที่ Yuki ลงบนจุดยอดสีดำในรอบการกระโดดที่ $i$

ตัวอย่าง

ข้อมูลนำเข้า 1

2
5 1
01010
3 5
2 1
1 3
3 4
9 3
100010000
1 2
2 3
2 4
3 5
3 6
4 7
6 8
7 9

ข้อมูลส่งออก 1

0 1 1 2
1 1 1 0 1 1 1 2

หมายเหตุ

สำหรับกรณีทดสอบแรก:

• ในรอบการกระโดดที่ $1$ ลำดับจุดยอดที่ไปเยือนที่ถูกต้องลำดับหนึ่งคือ $1,2$

• ในรอบการกระโดดที่ $4$ ลำดับจุดยอดที่ไปเยือนที่ถูกต้องลำดับหนึ่งคือ $1,3,5$

สำหรับกรณีทดสอบที่สอง:

• ในรอบการกระโดดที่ $4$ ลำดับจุดยอดที่ไปเยือนที่ถูกต้องลำดับหนึ่งคือ $1,5$

• ในรอบการกระโดดที่ $7$ ลำดับจุดยอดที่ไปเยือนที่ถูกต้องลำดับหนึ่งคือ $1,5,8$

• ในรอบการกระโดดที่ $8$ ลำดับจุดยอดที่ไปเยือนที่ถูกต้องลำดับหนึ่งคือ $1,4,9$