|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
There are $n$ contestants participating in a round robin competition. Each pair of contestants face each other only once. In each match there is only one winner, (there are no ties).
Given a subset of contestants $X$ and the winners of the matches between these contestants, it is said that the best player of $X$ cannot be determined if there is no contestant with more wins than the rest.
It is desired to find, given the results of all the matches made in the competition, a set of $3$ contestants where the best contestant cannot be determined.
Input
The first line contains an integer $1 \le n \le 2000$. The amount of contestants in the competition.
The next $ n $ lines represent the results of player $i$-th against the other contestants.
If the $j$-th character in the $i$-th line is $1$, it means that the contestant $i$ defeated the contestant $j$, if it is a $0$ it means he lost. For each pair of distinct contestants $i$ and $j$, it is guaranteed that either $i$ defeats $j$ or $j$ defeats $i$ (but not both).
Output
Print three integers $a,b,c$ ($1 \le a, b, c \le n$), the indices of the players that satisfy that a better player cannot be selected among them. If there are multiple answers, print any. If there is no solution to the problem, print $-1 $.
Sample test(s)
Input
4
0110
0000
0101
1100
Output
1 3 4
Input
4
0111
0000
0101
0100
Output
-1