토로이드 그리드

$m \times n$ 직사각 그리드는 $x$좌표가 $0$부터 $n-1$까지의 정수이고 $y$좌표가 $0$부터 $m-1$까지의 정수인 평면 위 점에 대응하는 정점을 가지며, 대응하는 두 점 사이의 거리가 $1$인 두 정점 사이에만 에지가 있는 그래프다. 이 그리드는 $m$개 행 각각에 $n$개의 정점이 있고, $n$개 열 각각에 $m$개의 정점이 있다. 행 $i$, 열 $j$에 있는 정점을 $(i,j)$로 나타낸다. 여기서 $0 \le i \le m-1$이고 $0 \le j \le n-1$이다.

모든 행 $i$에 대해 두 정점 $(i,0)$과 $(i,n-1)$을 잇는 에지를 추가하고, 모든 열 $j$에 대해 두 정점 $(0,j)$와 $(m-1,j)$를 잇는 에지를 추가하면, 각 행은 길이 $n$인 사이클을 이루고 각 열은 길이 $m$인 사이클을 이룬다. 이렇게 만든 그래프를 $m \times n$ 토로이드 그리드라고 부른다. 에지가 서로 교차하지 않도록 이 그래프를 토러스 위에 그릴 수 있기 때문이다.

주어진 $m \times n$ 토로이드 그리드에서 모든 정점을 정확히 한 번씩 지나는 사이클을 찾는 프로그램을 작성하시오. 이 사이클은 서로 다른 $mn$개 정점의 열 $(v_1, v_2, \ldots, v_{mn})$으로 나타내며, $1 \le k \le mn-1$인 모든 $k$에 대해 $v_k$와 $v_{k+1}$이 인접하고 $v_{mn}$과 $v_1$도 인접해야 한다.

표준입력에서 데이터를 읽는다. 첫째 줄에 테스트 데이터의 개수를 나타내는 정수 $T$가 주어진다. 이어지는 $T$개의 줄에는 각각 두 정수 $m$과 $n$이 주어지며, 그 줄의 입력 그래프가 $m \times n$ 토로이드 그리드임을 가리킨다. 여기서 $3 \le m, n \le 100$이다.

표준출력으로 데이터를 출력한다. 각 테스트 데이터마다 먼저 조건을 만족하는 해가 존재하는지를 나타내는 정수를 한 줄에 출력한다. 해가 존재하면 1, 존재하지 않으면 -1이다. 그 줄이 1일 때에만 이어서 사이클의 정점 열을 $mn$개의 줄에 출력한다. 정점 $(i,j)$는 공백 없이 (i,j) 형태로 출력한다. 어떤 줄에도 공백 문자(빈칸이나 탭)는 허용되지 않는다.

토로이드 그리드에는 이런 사이클이 여러 개 있으므로, 다음 한 가지만 정답으로 인정한다.

• $(0,0)$에서 시작한다.
• 각 행에서 열 $0$부터 열 $n-2$까지만 뱀 모양으로 훑는다. 행 $0$은 열 $0$에서 열 $n-2$ 방향으로, 행 $1$은 열 $n-2$에서 열 $0$ 방향으로 진행하고, 이렇게 방향을 번갈아 바꾼다. 한 행을 마치면 열을 바꾸지 않고 바로 아래 행으로 내려가 그 행을 훑는다.
• 행 $m-1$까지 마친 다음 $(m-1,n-1)$로 이동하고, 열 $n-1$을 $(m-1,n-1)$에서 $(0,n-1)$까지 위로 올라가며 방문한다.
• 마지막 정점 $(0,n-1)$은 행 $0$의 순환 에지로 $(0,0)$과 인접하므로 사이클이 닫힌다.

$3 \le m, n \le 100$인 토로이드 그리드에는 이런 사이클이 항상 있으므로, 각 테스트 데이터의 첫 줄은 언제나 1이다.