19702번 - 친구 스페셜 저지

문제

선린인터넷고등학교에는 $N$명의 학생들이 있다. $N$명의 학생들 가운데 일부는 서로를 좋아한다. 신기한 사실이 있는데, 학생들 간에 일방적으로 좋아하는 경우는 없고, 반드시 서로 좋아하거나, 혹은 서로 좋아하지 않는다고 한다.

어느 날, $N$명의 학생들이 둥근 원탁 위에 앉아 식사를 하고자 한다. 원탁 주위에는 $N$개의 자리가 있으며, 위 그림과 같이 원형으로 배치되어 있다.

어떤 학생이 자리 배치를 만족스럽게 느낄 조건은 자신의 양 옆에 자신이 좋아하는 학생이 앉아있는 것이라 한다. 모든 학생들이 만족스럽게 자리를 배치할 수 있을지 알아보자.

입력

학생 수를 나타내는 정수 $N$이 주어진다. 편의상 학생에 번호를 붙여 생각하자.

각 $i$ (1ドル \le i \le N$)에 대해 $i+1$번째 줄에는 $N$개의 정수 $a_{i, 1}, \dots, a_{i, N}$ 이 주어진다. $a_{i, j}$가 1ドル$이라면 학생 $i$가 학생 $j$를 좋아함을 의미하고, 0ドル$이라면 학생 $i$가 학생 $j$를 좋아하지 않음을 의미한다.

참고로, $a_{i, i} = 0$이며, 문제의 조건에 의해 $a_{i, j} = a_{j, i}$이다.

그리고 각 $i(1 \le i \le N)$에 대해 $\displaystyle \sum_{j=1}^{N} a_{i, j} \ge {N \over 2}$임이 보장된다.

출력

모든 학생이 만족스럽게 자리를 배치할 방법이 존재한다면, 1ドル$번 자리에 앉는 학생의 번호부터 $N$번 자리에 앉는 학생의 번호까지 사이에 공백을 두고 출력하라.

만약 모든 학생이 만족스럽게 자리를 배치할 방법이 존재하지 않는다면, $-1$을 출력하라.

제한

• 3ドル \le N \le 100$
• $a_{i, j} = 0$ 또는 $a_{i, j} = 1$

힌트