M. DPFIGHT – Giải đấu cờ vua

Đoàn trường THPT Chuyên Sơn La tổ chức giải đấu cờ vua. Sau vòng đấu loại, BTC chọn ra được bạn vào vòng chung kết, đánh số từ đến . Hình thức thi đấu ở vòng chung kết như sau: BTC cho bạn xếp thành một vòng tròn theo thứ tự (bạn thứ đứng cạnh bạn thứ ). Sau đó BTC sẽ chọn ngẫu nhiên bạn đứng cạnh nhau để đánh một ván loại trực tiếp, bạn thua sẽ bị loại ra khỏi vòng tròn. Bạn nào còn lại cuối cùng sẽ là bạn vô địch. Do đã nắm được lực cờ của từng bạn nên BTC đã biết được nếu bạn đấu với bạn thì ai sẽ là người chiến thắng. Cho biết ma trận với ý nghĩa:

• nếu thắng , ngược lại nếu thắng
• với mọi
• với mọi

BTC rất muốn biết những bạn nào có khả năng vô địch giải đấu, bạn hãy giúp BTC trả lời câu hỏi này nhé.

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương ;
• dòng tiếp theo là ma trận . Dòng thứ chứa số nguyên , hai số liên tiếp ghi cách nhau một dấu cách.

Dữ liệu ra:

• Dòng đầu ghi số nguyên dương là số bạn có khả năng vô địch.
• Dòng thứ hai ghi chỉ số của những bạn có khả năng vô địch theo thứ tự tăng dần, hai số liên tiếp cách nhau một dấu cách.

Ví dụ:

Dữ liệu vào:

3
1 1 0
0 1 1
1 0 1

Dữ liệu ra:

3
1 2 3

Dữ liệu vào:

7
1 1 1 1 1 0 1
0 1 0 1 1 0 0
0 1 1 1 1 1 1
0 0 0 1 1 0 1
0 0 0 0 1 0 1
1 1 0 1 1 1 1
0 1 0 0 0 0 1

Dữ liệu ra:

3
1 3 6

Giải thích:

• Trong test : Tương quan thắng thua của bạn như hình sau (Mũi tên chỉ vào ai là người đó thắng)

• Nếu ta chọn đấu với thắng, tiếp theo là đấu với thắng vô địch
• Nếu ta chọn đấu với thắng, tiếp theo là đấu với thắng vô địch
• Nếu ta chọn đấu với thắng, tiếp theo là đấu với thắng vô địch

Giới hạn:

• .