시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 940 381 317 43.544%

문제

m × n 직사각 그리드(rectangular grid)는, x-좌표의 범위가 0부터 n-1까지인 정수이고 y-좌표의 범위가 0부터 m-1까지 정수인 평면상의 점들에 대응하는 정점들을 가지고, 두 정점에 대응하는 두 점 사이의 거리가 1 일 때에만 그 둘을 잇는 에지가 있는 그래프다. 예를 들어, 4 × 6 직사각 그리드가 그림 1 에 있다. 이 그리드는 m개 행 각각에 n개의 정점이 있고, n개 열 각각에 m 개의 정점이 있다. 행 i와 열 j에 있는 정점을 (i,j)라고 나타낸다. 여기서 0 ≤ i ≤ m-1이고 0 ≤ j ≤ n-1이다.

m × n 직사각 그리드의 모든 행 i ∈ {0, … , m-1}에 대하여 두 정점 (i, 0)과 (i, n-1)을 잇는 에지를 추가하고, 또한 모든 열 j ∈ {0, … , n-1} 에 대하여 두 정점 (0, j) 와 (m-1, j) 을 잇는 에지를 추가하면, 그림 2 에 보인 것과 같이 각 행은 길이 n인 사이클을 이루고 각 열은 길이 m인 사이클을 이루게 된다. 이렇게 만들어진 그래프를 종종 m × n 토로이드 그리드(toroidal grid) 라고 부르는데, 왜냐하면 이 그래프를 토러스(torus)에 에지가 교차하지 않도록 그릴 수 있기 때문이다.

주어진 m × n 토로이드 그리드에 대하여, 모든 정점을 정확히 한번씩 지나는 사이클을 찾는 프로그램을 작성하시오. 문제에서 요구하는 사이클은 그래프에 있는 서로 다른 mn개 정점들의 열 (v1, v2, … , vmn)로 나타낼 수 있는데, 이때 모든 k ∈ {1, … , mn-1}에 대하여 vk와 vk+1은 인접하며 또한 vmn과 v1도 인접하여야 한다.

입력

표준입력에서 데이터를 읽는다. 입력은 T개의 의 테스트 데이터로 구성되어 있다. 입력의 첫째 줄에 입력 데이터의 개수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 두 정수 m과 n을 포함하는 한 줄로 구성되어 있는데, 입력 그래프가 m × n 토로이드 그리드임을 가리킨다. 여기서 3 ≤ m, n ≤ 100이다.

출력

표준출력으로 데이터를 출력한다. 각 테스트 데이터에 대해, 출력의 첫째 줄에는 조건을 만족하는 해가 존재하는지 아닌지를 나타내는 정수를 출력해야 한다. 만약 해가 존재하면, 그 정수는 1 이어야 한다; 그렇지 않으면 -1 이다. 첫째 줄이 1 일 경우에만 추가로 문제에서 요구한 사이클의 정점 열(sequence)을 mn 개의 줄에 출력한다. 복수의 해가 가능하면, 그 중 임의의 하나를 출력하면 된다. 어떤 줄에도 공백 문자(빈칸이나 탭)는 허용되지 않는다.

예제 입력

2
3 4
3 3

예제 출력

1
(0,0)
(0,1)
(1,1)
(1,2)
(0,2)
(0,3)
(1,3)
(2,3)
(2,2)
(2,1)
(2,0)
(1,0)
1
(2,2)
(2,0)
(1,0)
(0,0)
(0,1)
(0,2)
(1,2)
(1,1)
(2,1)

힌트