MUSKET - Musketeers

#### 题目背景 在路易十三与红衣主教黎塞留的时代，$n$个火枪手已经吃完了饭，正在一起喝酒。葡萄酒的供应很充足导致醉酒的火枪手们发生了争执，一场醉酒的争执爆发，每个火枪手都冒犯了其他所有人。 决斗已经不可避免了，但是谁应该与谁，以及应该以什么顺序进行决斗？他们决定（在自从他们成为战友以来的第一次决斗中）围成一个圆圈并按顺序抽签。一个抽到签的火枪手与右边的人进行决斗。失败者，用不那么血腥的话来讲，“退出游戏”，切确地说，他的尸体被仆人带走了。站“退出游戏”的人旁边的下一个火枪手成了胜利者的邻居。 多年以后，当历史学家阅读胜利者所撰写的回忆录时，他们意识到最终结果在很大程度上依赖于决斗的顺序。他们注意到平时的训练已经表明了谁能够赢得决斗。似乎（在数学语言中）“A 能战胜 B”的关系不是传递性的！这就意味着，可能会发生火枪手A战胜B，B战胜C和C战胜A。当然，其中三个中的第一个决斗影响了最终结果。如果A和B作为第一个战斗，C最终胜出。但如果B和C作为第一个战斗，A终于获胜。历史学家着迷于他们的发现，并决定设法验证哪些火枪手可能存活下来。法国和整个文欧洲明的命运皆取决于此！ #### 题目描述 现在有$n$个人，他们按照逆时针顺序围成一圈。他们要进行$n-1$场决斗。 在第一轮中，这些人中的第$i$人与右边的邻居决斗，即与编号为$i + 1$的人（如果$i=n$，那么则与第$1$个人决斗）。 失败者“退出游戏”，圆圈缩小，站“退出游戏”的人旁边的下一个人成了胜利者的邻居。我们以矩阵的形式给出了可能的决斗结果。 如果$A_{i,j} = 1$那么第$i$个人与第$j$个人决斗时，第$i$个人获胜。 $A_{i,j} = 0$则反之。我们可以说，一定存在一个数$k$，第$k$人可以赢得比赛，赢得最后的胜利。 写一个程序： 从标准输入中读取矩阵$A$， 计算可能赢得比赛的人， 将它们写入标准输出。 #### 输入格式 第一行，一个整数$t$，表示总共有$t$组数据 在每组数据中，第一行输入一个整数$n$，表示有$n$个火枪手 接下来的$n$行中，每行有$n$个数（不含空格），第$i$行的第$j$个数为$A_{i,j}$的值。当然$A_{i,j} = 1 - A_{j,i}$。我们约定对于每一个$i$，$A_{i,i} = 1$ #### 输出格式 对于每组数据，第$1$行应输出一个数$m$，表示可能胜出的人数 接下来的$m$行中，每行$1$个数，表示胜利者的编号 #### 说明/提示 $3<= n <= 100$ 感谢 @智子 提供更佳的翻译

In the time of Louis XIII and his powerful minister cardinal Richelieu in the Full Barrel Inn _n_ musketeers had consumed their meal and were drinking wine. Wine had not run short and therefore the musketeers were eager to quarrel, a drunken brawl broke out, in which each musketeer insulted all the others. A duel was inevitable. But who should fight who and in what order? They decided (for the first time since the brawl they had done something together) that they would stay in a circle and draw lots in order. A drawn musketeer fought against his neighbor to the right. A looser "quit the game" and to be more precise his corpse was taken away by servants. The next musketeer who stood beside the looser became the neighbor of a winner. After years, when historians read memories of the winner they realized that a final result depended in a crucial extent on the order of duels. They noticed that a fence practice had indicated, who against who could win a duel. It appeared that (in mathematical language) the relation "**A** wins **B**" was not transitive! It could happen that the musketeer **A** fought better than **B**, **B** better than **C** and **C** better than **A**. Of course, among three of them the first duel influenced the final result. If **A** and **B** fight as the first, **C** wins eventually. But if **B** and **C** fight as the first, **A** wins finally. Historians fascinated by their discovery decided to verify which musketeers could survive. The fate of France and the whole civilized Europe indeed depended on that! ### Task _N_ persons with consecutive numbers from _1_ to _n_ stay in a circle. They fight _n-1_ duels. In the first round one of these persons (e.g. with the number _i_) fights against its neighbor to the right, i.e. against the person numbered _i+1_ (or, if _i=n_, against the person numbered _1_). A looser quits the game, and the circle is tighten so that the next person in order becomes a winner's neighbor. We are given the table with possible duels results, in the form of a matrix. If **A**_i,j_ = 1 then the person with the number _i_ always wins with the person _j_. If **A**_i,j_ = 0 the person _i_ looses with _j_. We can say that the person _k_ may win the game if there exists such a series of _n-1_ drawings, that _k_ wins the final duel. Write a program which: - reads matrix **A** from the standard input, - computes numbers of persons, who may win the game, - writes them into the standard output.

The number of test cases t is in the first line of input, then t test cases follow separated by an empty line. In the first line of each test case integer _n_ which satisfies the inequality _3<=n<=100_ is written. In each of the following _n_ lines appears one word consisting of _n_ digits 0 or 1. A digit on _j_-th position in _i_-th line denote **A**_i,j._ Of course **A**_i,j_ = 1 - **A**_j,i_, for _i<>j_. We assume that **A**_i,i_ = 1, for each _i_.

For each test case in the first line there should be written _m_ - the number of persons, who may win the game. In the following _m_ lines numbers of these persons should be written in ascending order, one number in each line.

1
7
1111101
0101100
0111111
0001101
0000101
1101111
0100001

3
1
3
6