스위치

여행을 좋아하는 Alice는 아주 흥미로운 호텔에 묵게 되었다. 이 호텔에 묵으려는 손님은 모두 자신이 묵을 방에 설치된 조명에 관한 퀴즈를 풀어야 한다. 호텔 프런트는 손님에게 묵을 방에 설치된 조명과 그 조명에 연결된 스위치에 관한 정보를 준다. 그 정보에 따르면 하나의 스위치에는 하나 이상의 조명이 연결되어 있고, 각 조명에도 하나 이상의 스위치가 연결되어 있다.

Alice가 묵을 방에는 N개의 조명과 N개의 스위치가 있다. 흥미로운 점은 Alice가 스위치 하나를 켜면 조명 하나만 켜지는 것이 아니라 여러 조명이 동시에 켜진다는 것이다. 또한 스위치가 하나 이상 켜져 있는 상태에서 다른 스위치를 켜면 이미 켜져 있던 조명이 꺼질 수도 있다. 다행히 모든 스위치가 꺼져 있으면 모든 조명도 꺼져 있다.

그림 J.1은 N = 5일 때 Alice가 호텔 프런트에서 받은 정보의 한 예이다.

그림 J.1

각 조명이 스위치로부터 어떻게 영향을 받는지 알아내기 위해 Alice는 다음과 같이 실험한다. 먼저 각 조명과 각 스위치에 번호를 붙여 구별할 수 있게 한다. 그런 다음 모든 스위치를 끈 상태에서 스위치 1번만 켜서 어떤 조명이 켜지는지 확인한다. 이어서 스위치 1번을 끄고 스위치 2번을 켜서 어떤 조명이 켜지는지 확인한다. 다시 스위치 2번을 끄고 스위치 3번을 켜는 식으로 반복하여 각 스위치가 어떤 조명을 켜는지 확인한다.

그다음에는 스위치를 둘 이상 켜서 어떤 규칙이 있는지 알아낸다. 그 결과 각 조명은 자신에게 연결된 스위치에 의해 토글된다는 것을 알게 되었다. 이 규칙은 다음과 같다.

• 조명은 자신에게 연결된 스위치 중 켜져 있는 것의 개수가 홀수(짝수)이면 켜진다(꺼진다).

예를 들어 그림 J.1의 연결 정보에서 조명 1번이 어떻게 동작하는지 살펴보자. 조명 1번은 스위치 1번, 2번, 5번을 각각 켜면 켜진다. 다른 스위치(스위치 2번과 5번)가 모두 꺼져 있는 상태에서 스위치 1번을 켜면 조명 1번은 켜진다. 여기서 스위치 2번을 추가로 켜면 조명 1번은 꺼진다. 다시 스위치 5번을 추가로 켜면(즉 세 스위치가 모두 켜져 있으면) 조명 1번은 다시 켜진다. 이런 식으로 스위치를 조작하는 동안 다른 조명의 상태도 바뀔 수 있다.

Alice는 각 조명에 대해 스위치를 조작하여 그 조명만 켜고 나머지 조명은 모두 끄는 것이 가능한지 궁금해한다.

스위치와 조명의 연결 정보가 주어졌을 때 Alice를 도와줄 프로그램을 작성하라. 즉, 각 조명에 대해 스위치를 조작하여 그 조명만 켜고 나머지 조명은 모두 끄는 것이 가능한지 판별하는 프로그램을 작성하라.

프로그램은 표준 입력에서 입력을 읽는다. 첫째 줄에 정수 N (3 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각각 0과 1로 이루어진 N개의 정수가 하나의 공백을 사이에 두고 주어진다. i번째(1 ≤ i ≤ N) 줄의 수는 i번째 스위치에 어떤 조명이 연결되어 있는지를 나타낸다. i번째 줄의 k번째(1 ≤ k ≤ N) 값이 1이면 k번째 조명이 i번째 스위치에 연결되어 있다는 뜻이고, 0이면 연결되어 있지 않다는 뜻이다.

프로그램은 표준 출력에 출력을 쓴다. 모든 조명에 대해 스위치를 조작하여 그 조명만 켜고 나머지 조명은 모두 끄는 것이 가능하면, 켜야 하는 스위치 번호를 증가하는 순서로 출력한다. 그렇지 않으면 다음 예시와 같이 -1을 출력한다. 출력이 -1이 아닌 경우, k번째 줄의 스위치 번호는 k번째 조명을 켜는 스위치들이어야 한다. 정답이 여러 개면 그중 아무거나 출력한다.