โจทย์ข้อนี้เป็นโจทย์แบบโต้ตอบ (Interactive Problem)

Little Cyan Fish มีกราฟไม่มีทิศทางอย่างง่ายที่มีจุดยอด $n$ จุด หมายเลขตั้งแต่ $1$ ถึง $n$ และเส้นเชื่อม $m$ เส้น หมายเลขตั้งแต่ $1$ ถึง $m$ ในตอนเริ่มต้น สีของจุดยอด $i$ คือ $i$

ผู้เล่นสองคน คือ A และ B เล่นเกมที่ประกอบด้วย $m$ รอบ ในแต่ละรอบ ผู้เล่นทั้งสองจะทำสิ่งต่อไปนี้ตามลำดับ:

• ผู้เล่น A เลือกเส้นเชื่อม $(u, v)$ ที่ยังไม่เคยถูกเลือกในรอบใด ๆ ก่อนหน้านี้
• ผู้เล่น B เลือกจุดปลายด้านหนึ่งของเส้นเชื่อมนี้ แล้วเปลี่ยนสีของจุดยอดนั้นให้เป็นสีปัจจุบันของจุดปลายอีกด้านหนึ่ง

หลังจากครบทั้ง $m$ รอบ ผู้เล่น B จะชนะหากจุดยอดทั้งหมดมีสีเดียวกัน มิฉะนั้น ผู้เล่น A จะชนะ

Little Cyan Fish ต้องการให้คุณระบุว่าผู้เล่นคนใดสามารถรับประกันชัยชนะได้เสมอไม่ว่าผู้เล่นอีกฝ่ายจะเดินอย่างไร จากนั้นจงเล่นเป็นผู้เล่นคนนั้นแข่งกับเขาและเอาชนะเกมให้ได้

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

มีข้อมูลทดสอบหลายชุด บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็มหนึ่งตัวคือ $T$ ($1 \le T \le 10^4$) แสดงจำนวนชุดข้อมูลทดสอบ

สำหรับข้อมูลทดสอบแต่ละชุด บรรทัดแรกประกอบด้วยจำนวนเต็มสองตัวคือ $n$ และ $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$) แสดงจำนวนจุดยอดและจำนวนเส้นเชื่อมตามลำดับ

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

รับประกันว่ากราฟไม่มีเส้นเชื่อมวนเข้าหาตัวเอง (self-loops) และไม่มีเส้นเชื่อมขนาน (multiple edges) กราฟอาจจะไม่เชื่อมโยงกัน (disconnected)

รับประกันว่าผลรวมของ $n$ จากข้อมูลทดสอบทุกชุดไม่เกิน $10^5$ และผลรวมของ $m$ จากข้อมูลทดสอบทุกชุดไม่เกิน $10^5$

หลังจากอ่านกราฟหนึ่งกราฟแล้ว จงทำการโต้ตอบสำหรับชุดข้อมูลทดสอบนั้นให้เสร็จสิ้นก่อนที่จะอ่านกราฟถัดไป

การโต้ตอบ

ในการเลือกบทบาทของคุณ ให้แสดงผลหนึ่งบรรทัดที่ประกอบด้วย A หรือ B แสดงผล A หากผู้เล่น A สามารถรับประกันชัยชนะได้ หรือแสดงผล B หากผู้เล่น B สามารถรับประกันชัยชนะได้ Little Cyan Fish จะเล่นเป็นผู้เล่นอีกฝ่ายหนึ่ง

จากนั้นจงเล่นเกมจำนวน $m$ รอบพอดีดังต่อไปนี้

• หากคุณเล่นเป็น A ให้แสดงผลหนึ่งบรรทัดที่ประกอบด้วยจำนวนเต็มหนึ่งตัวคือ $e$ ($1 \le e \le m$) ซึ่งเป็นหมายเลขของเส้นเชื่อมที่ยังไม่เคยถูกเลือกในรอบใด ๆ ก่อนหน้านี้ เพื่อเป็นการตอบกลับ คุณจะได้รับจำนวนเต็มหนึ่งตัวคือ $x$ ในหนึ่งบรรทัด จุดยอด $x$ เป็นจุดปลายด้านหนึ่งของเส้นเชื่อม $e$ และสีของมันจะเปลี่ยนเป็นสีปัจจุบันของจุดปลายอีกด้านหนึ่ง
• หากคุณเล่นเป็น B ให้อ่านจำนวนเต็มหนึ่งตัวคือ $e$ ($1 \le e \le m$) ในหนึ่งบรรทัด ซึ่งเป็นหมายเลขของเส้นเชื่อมที่ยังไม่เคยถูกเลือกในรอบใด ๆ ก่อนหน้านี้ ให้แสดงผลหนึ่งบรรทัดที่ประกอบด้วยจำนวนเต็มหนึ่งตัวคือ $x$ ซึ่งเป็นจุดปลายด้านหนึ่งของเส้นเชื่อม $e$ สีของจุดยอด $x$ จะเปลี่ยนเป็นสีปัจจุบันของจุดปลายอีกด้านหนึ่ง

หลังจากครบทั้ง $m$ รอบ ให้อ่านจำนวนเต็มหนึ่งตัว จำนวนเต็มนี้จะเป็น 1 หากคุณเลือกบทบาทถูกต้องและชนะเกม หลังจากได้รับ 1 ให้ดำเนินการต่อในชุดข้อมูลทดสอบถัดไป หลังจากชุดข้อมูลทดสอบสุดท้าย โปรแกรมของคุณควรจบการทำงาน

ตัวตรวจแบบโต้ตอบ (interactor) จะส่ง -1 หากคุณเลือกบทบาทไม่ถูกต้อง เดินหมากไม่ถูกต้องตามกติกา หรือแพ้เกม หากคุณได้รับ -1 ณ จุดใดก็ตาม โปรแกรมของคุณควรจบการทำงานทันที

หลังจากแสดงผลบทบาทหรือตาเดินของคุณ อย่าลืมแสดงผลอักขระขึ้นบรรทัดใหม่และล้างบัฟเฟอร์ข้อมูลส่งออก (flush)

เครื่องมือทดสอบ: มีเครื่องมือทดสอบเตรียมไว้ให้เพื่อช่วยให้ผู้เข้าแข่งขันพัฒนาและทดสอบคำตอบของตนเอง คุณสามารถดาวน์โหลดเครื่องมือนี้ได้จากไฟล์แนบ สั่งทำงานเครื่องมือด้วยตัวเลือก -h เพื่อแสดงคำแนะนำการใช้งาน เครื่องมือทดสอบนี้ครอบคลุมเพียงบางสถานการณ์ทดสอบและบางความสามารถที่ตัวตรวจแบบโต้ตอบทางการรองรับเท่านั้น

ตัวอย่าง

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

2
3 2
2 3
1 2

1

2

1
4 3
1 2
2 3
3 4


2

4

3
1

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

B

3

1






A
1

3

2

หมายเหตุ

เกมทั้งสองเกมในตัวอย่างแสดงอยู่ด้านล่าง ในแต่ละขั้นตอน A เลือกเส้นเชื่อมที่เน้นสี และ B เปลี่ยนสีของจุดยอดที่มีวงกลมล้อมรอบ เส้นเชื่อมแบบเส้นประคือเส้นเชื่อมที่ถูกเลือกไปแล้วก่อนหน้านี้