시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 13 11 8 88.889%

문제

축구 토너먼트에는 총 n개 팀이 참가한다. 첫 번째 라운드에서 총 n/2개의 경기가 열리게 된다. 매 라운드가 끝난 다음에, 승리한 팀은 다음 라운드에 진출한다. 두 번째 라운드에는 총 n/4개의 경기가 열리게 된다. 마지막에는 두 팀이 결승전에 올라오게 된다. 결승전의 승자는 토너먼트의 승자가 된다.

선영이는 한 축구 팀의 구단주이다. 이 팀은 세계에서 가장 축구를 잘하는 팀은 아니지만, 꽤 잘하는 팀이다. 선영이네 축구팀은 토너먼트에 참가한 팀중 적어도 절반은 쉽게 이길 수 있다. 또, 선영이네 팀이 이기지 못하는 모든 팀 t에 대해서, 그 팀을 이길 수 있으면서 선영이네 팀에게 지는 팀 t'가 항상 존재한다.

선영이네 팀이 토너먼트에 우승할 수 있게 토너먼트 스케줄을 작성하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 토너먼트에 참가하는 팀의 수 n이 주어진다. (2 ≤ n ≤ 1024, n은 2의 제곱꼴) 팀은 1번부터 n번까지 번호가 매겨져 있으며, 선영이네 팀의 번호는 1이다.

다음 n개 줄에는 n자리 바이너리 스트링이 주어진다. j번째 줄의 k번째 숫자가 1인 경우에는 팀 j가 팀 k를 이길 수 있는 것이고, 다른 경우는 모두 0이다. (토너먼트 경기이기 때문에, 비기는 경우는 존재하지 않는다)

팀은 자기 자신과 경기를 할 수 없기 때문에, j번째 줄의 j번째 숫자는 항상 0이다. j와 k가 다른 경우에, j번째 줄의 k번째 숫자와 k번째 줄의 j번째 숫자는 다르다.

출력

각 테스트 케이스에 대해서, 선영이네 팀이 승리할 수 있는 토너먼트 스케줄 n-1개 줄을 출력한다.

첫 n/2개 줄은 토너먼트의 첫 번째 라운드, 다음 n/4개 줄은 두 번째 라운드, ... 마지막 줄은 결승전이다.

각 줄은 두 정수 x와 y로 이루어져 있어야 한다. 이 뜻은 팀 x와 팀 y가 경기를 한다는 뜻이다.

만약, 팀1이 우승할 수 있는 스케줄이 여러가지인 경우 아무거나 출력한다.

예제 입력

4
0110
0011
0000
1010
8
00111010
10101111
00010010
01000101
00110010
10101011
00010000
10101010

예제 출력

1 3
2 4
1 2
1 5
3 7
4 8
2 6
1 3
4 2
1 4

힌트