"Astra" เป็นบอร์ดเกมที่สวยงามซึ่งผู้เล่นจะผลัดกันค้นพบกลุ่มดาวโดยการทำเครื่องหมายที่ดวงดาว เกมนี้เป็นการผสมผสานที่ชาญฉลาดระหว่างยุทธวิธีและกลยุทธ์ ด้วยชุดกฎที่กระชับและเข้าใจง่าย ทำให้เรียนรู้ได้ง่ายและเล่นได้รวดเร็ว

Photo by @kavics004 on BoardGameGeek

พิจารณาเกมสำหรับผู้เล่นสองคนระหว่าง Alice และ Bob ในเกมนี้มีกลุ่มดาวรูปต้นไม้ ซึ่งสามารถมองเป็นกราฟเชื่อมต่อที่ประกอบด้วยดวงดาว $n$ ดวง (หมายเลขตั้งแต่ $1$ ถึง $n$) และเส้นเชื่อม $(n - 1)$ เส้น ในตอนเริ่มต้น มีเพียงดาวดวงเดียวคือ $s$ ที่ถูกทำเครื่องหมายไว้ Alice และ Bob จะผลัดกันทำเครื่องหมายดาวที่เหลือตามกฎต่อไปนี้:

• ในแต่ละเทิร์น ผู้เล่นจะต้องทำเครื่องหมายดาวอย่างน้อย $1$ ดวง และมากที่สุด $k$ ดวง
• ดาวแต่ละดวงสามารถถูกทำเครื่องหมายได้เพียงครั้งเดียวเท่านั้น
• ให้ $a_1, a_2, \cdots, a_p$ เป็นดาวที่ถูกทำเครื่องหมายในหนึ่งเทิร์น ตามลำดับที่ถูกทำเครื่องหมาย:
  • เมื่อทำเครื่องหมาย $a_1$ ดาวดวงนั้นจะต้องเป็นเพื่อนบ้านของดาวที่ถูกทำเครื่องหมายไว้แล้ว
  • สำหรับทุก $2 \le i \le p$ เมื่อทำเครื่องหมาย $a_i$ ดาวดวงนั้นจะต้องเป็นเพื่อนบ้านของ $a_{i-1}$

ดาวสองดวง $u$ และ $v$ เป็นเพื่อนบ้านกันหากมีเส้นเชื่อมเชื่อมต่อกันโดยตรง

ผู้เล่นที่ทำเครื่องหมายดาวดวงสุดท้ายจะเป็นผู้ชนะในกลุ่มดาวนั้น กำหนดให้ Alice เป็นผู้เล่นคนแรกและผู้เล่นทั้งสองเล่นอย่างเหมาะสมที่สุด สำหรับแต่ละ $1 \le s \le n$ จงหาว่าใครจะเป็นผู้ชนะในกลุ่มดาวนั้น

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

มีหลายกรณีทดสอบ บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 100$) ซึ่งระบุจำนวนกรณีทดสอบ สำหรับแต่ละกรณีทดสอบ:

บรรทัดแรกประกอบด้วยจำนวนเต็มสองตัวคือ $n$ และ $k$ ($2 \le n \le 2 \times 10^3$, $1 \le k < n$) ซึ่งระบุจำนวนดวงดาวและจำนวนดวงดาวสูงสุดที่สามารถทำเครื่องหมายได้ในแต่ละเทิร์น

สำหรับ $(n - 1)$ บรรทัดถัดไป บรรทัดที่ $i$ ประกอบด้วยจำนวนเต็มสองตัวคือ $u_i$ และ $v_i$ ($1 \le u_i, v_i \le n$) ซึ่งระบุว่ามีเส้นเชื่อมระหว่างดาว $u_i$ และ $v_i$

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

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

สำหรับแต่ละกรณีทดสอบ ให้แสดงผลหนึ่งบรรทัดที่ประกอบด้วยสตริง $d_1 d_2 \cdots d_n$ ($d_i \in \{0, 1\}$) โดยที่ $d_i$ ระบุว่าใครจะเป็นผู้ชนะในกลุ่มดาวเมื่อ $s = i$ หาก Alice ชนะแล้ว $d_i = 1$; มิฉะนั้นหาก Bob ชนะแล้ว $d_i = 0$

ตัวอย่าง

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

3
6 2
1 2
3 2
3 4
5 3
2 6
3 1
1 2
2 3
3 2
1 2
2 3

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

011000
000
101

หมายเหตุ

กรณีทดสอบตัวอย่างแรกแสดงอยู่ในภาพด้านบน

• พิจารณา $s = 1$ ในเทิร์นแรก Alice มีสามทางเลือก: ทำเครื่องหมาย $\{2\}$, $\{2, 3\}$ หรือ $\{2, 6\}$ หาก Alice เลือก $\{2, 6\}$ จากนั้น Bob สามารถทำเครื่องหมาย $\{3\}$ และจะเหลือดาวที่แยกจากกัน $2$ ดวง ในเทิร์นถัดๆ ไป ผู้เล่นแต่ละคนจะสามารถทำเครื่องหมายดาวได้เพียงครั้งละหนึ่งดวงเท่านั้น และ Bob จะเป็นผู้ชนะ ทางเลือกอื่นๆ ของ Alice สามารถวิเคราะห์ได้ในทำนองเดียวกัน
• พิจารณา $s = 2$ ในเทิร์นแรก Alice มีห้าทางเลือก: ทำเครื่องหมาย $\{1\}$, $\{3\}$, $\{6\}$, $\{3, 4\}$ หรือ $\{3, 5\}$ Alice สามารถเลือกทำเครื่องหมาย $\{3\}$ และจะเหลือดาวที่แยกจากกัน $4$ ดวง ในเทิร์นถัดๆ ไป ผู้เล่นแต่ละคนจะสามารถทำเครื่องหมายดาวได้เพียงครั้งละหนึ่งดวงเท่านั้น และ Alice จะเป็นผู้ชนะ

สำหรับกรณีทดสอบตัวอย่างที่สอง เนื่องจาก $k = 1$ จะมีเทิร์นทั้งหมด $3 - 1 = 2$ เทิร์นพอดี ดังนั้น Bob จึงเป็นผู้ชนะเสมอ

สำหรับกรณีทดสอบตัวอย่างที่สาม หาก $s = 1$ หรือ $s = 3$ Alice สามารถทำเครื่องหมายดาวที่เหลืออีก $2$ ดวงได้โดยตรงและชนะกลุ่มดาวนั้นทันที