The Earth Rumble tournament is a king-of-the-hill style tournament where two competitors face each other in each round and the winner moves on to face a new competitor in the next round. The winner of the final pairing is crowned the Earthbending champion.
The strengths of each competitor are mostly set it stone, so the organisers of the tournament know who the winner would be in any pairing of competitors. They would like to make their tournament as exciting as possible by ordering the competitors so that no person wins two rounds in a row. Could you help them find such an ordering?
Input Specification
The first line of input contains one integer , the number of competitors. The next lines each contain integers such that the entry of the line is if competitor beats competitor and otherwise.
Output Specification
A single line containing an ordering of the competitors as described in the problem statement, or -1
if no such ordering exists.
Sample Input 1
2
0 1
0 0
Sample Output 1
1 2
Sample Input 2
4
0 0 1 1
1 0 1 1
0 0 0 1
0 0 0 0
Sample Output 2
3 4 1 2
Comments