ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Open Personal Contest 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Fat Hobbits

Time limit: 1.0 second
Memory limit: 64 MB
None of the hobbits can fight Mordor's army on his own. Gandalf have chosen N hobbits from Shire to form a platoon that will go on a new campaign against Mordor. But some of the hobbits refuse to go because they are afraid that other hobbits in the platoon will call them fat. More exactly, each hobbit refuses to go on the campaign if there will be at least one hobbit with smaller weight in the platoon. Fortunately, hobbits don't know their exact weights. They can only compare their weights using a pan balance, and there is only one pan balance in Shire. Some pairs of hobbits used it to determine which of them was heavier. All hobbits know the results of all weighings. Gandalf is sure that there are no two hobbits with the same weight. Help Gandalf to choose from the N hobbits as many hobbits as possible provided that they will agree to go on the campaign together. Remember that hobbits are clever creatures and know that if, for example, Sam is heavier than Pippin and Pippin is heavier than Frodo, then Sam is heavier than Frodo.


The first line contains the number N of hobbits which were primarily chosen by Gandalf (2 ≤ N ≤ 100). The hobbits are numbered from 1 to N. In the next N lines there is a matrix N × N, which shows the results of weighings. If hobbits with numbers i and j weighed themselves against each other and it turned out that hobbit i was heavier, then there is 1 at the intersection of row i and column j. All other elements are zeros.


In the first line output the maximal number of hobbits in the platoon. In the second line, give their numbers.


0 1
0 0
0 0 0
0 0 0
0 0 0
1 2 3
Problem Author: Alexander Ipatov
Problem Source: VIII USU Open Personal Contest (March 3, 2007)
To submit the solution for this problem go to the Problem set: 1533. Fat Hobbits