CERC12

Kingdom (Problem A)

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

มีอาณาจักรอยู่ N แห่ง สำหรับคู่อาณาจักร (A,B) ใด ๆ จำนวนเงินที่ A เป็นลูกหนี้ B คือจำนวนเต็ม $D_{AB}$ โดยเราจะถือว่า $D_{AB}=-D_{BA}$ ถ้าอาณาจักรใดมีสถาณะการเงินสุทธิเป็นติดลบ (คือจำนวนเงินที่เป็นลูกหนี้ มากกว่า จำนวนเงินที่เป็นเจ้าหนี้) อาณาจักรนั้นอาจจะล้มละลายได้ ถ้าอาณาจักรล้มละลาย สถานะการเป็นหนี้ของอาณาจักรนั้น (ทั้งเจ้าหนี้และลูกหนี้) จะถือว่ายกเลิกไปทั้งหมด หลังจากอาณาจักรหนึ่งล้มละลายไป มันอาจจะทำให้อาณาจักรอื่น ๆ ล้มละลายตามกันไปด้วย จนกระทั่งเข้าสู่สถานะเสถียรซึ่งไม่มีอาณาจักรใดสามารถล้มละลายได้อีก

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

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

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

• บรรทัดแรกประกอบด้วยจำนวนเต็ม N (1 <= N <= 20) ซึ่งระบุจำนวนของอาณาจักร
• หลังจากนั้นอีก N บรรทัด แต่ละบรรทัดจะมีจำนวนเต็ม N ตัว จะระบุข้อมูลของหนี้ระหว่างแต่ละอาณาจักร จำนวนเต็มตัวที่ j ในบรรทัดที่ i คือค่า $d_{ij}$ จำนวนเงินที่อาณาจักร i เป็นลูกหนี้ของอาณาจักร j รับประกันว่า $d_{ii}=0$ และ $d_{ij}=-d_{ji}$ สำหรับ $1<=i,j<=N$และ $d_{ij}<=10^{6}$

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

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

ตัวอย่าง

ข้อมูลนำเข้า	ข้อมูลส่งออก
1 3 0 -3 1 3 0 -2 -1 2 0	1 3