Toroidal grid

The $m \times n$ rectangular grid is the graph whose vertices correspond to the points of the plane with an integer $x$ coordinate from $0$ to $n-1$ and an integer $y$ coordinate from $0$ to $m-1$, and which has an edge between two vertices exactly when the distance between their two points is $1$. The grid has $n$ vertices in each of its $m$ rows and $m$ vertices in each of its $n$ columns. The vertex in row $i$ and column $j$ is written $(i,j)$, where $0 \le i \le m-1$ and $0 \le j \le n-1$.

Add an edge between $(i,0)$ and $(i,n-1)$ for every row $i$, and an edge between $(0,j)$ and $(m-1,j)$ for every column $j$. Every row then forms a cycle of length $n$ and every column forms a cycle of length $m$. The graph built this way is called the $m \times n$ toroidal grid, because you can draw it on a torus with no two edges crossing.

Write a program that, for a given $m \times n$ toroidal grid, finds a cycle passing through every vertex exactly once. Such a cycle is a sequence $(v_1, v_2, \ldots, v_{mn})$ of $mn$ distinct vertices in which $v_k$ and $v_{k+1}$ are adjacent for every $k$ with $1 \le k \le mn-1$, and $v_{mn}$ and $v_1$ are adjacent as well.

Read the data from standard input. The first line has one integer $T$, the number of test cases. Each of the next $T$ lines has two integers $m$ and $n$, meaning that the input graph on that line is the $m \times n$ toroidal grid. Here $3 \le m, n \le 100$.

Write the data to standard output. For each test case, first print on its own line one integer telling whether a cycle exists: 1 if it does, -1 if it does not. Only when that line is 1, print the vertex sequence of the cycle on the next $mn$ lines. Print the vertex $(i,j)$ as (i,j) with no space. No line may contain a whitespace character (a blank or a tab).

A toroidal grid has many such cycles, so exactly one of them is accepted.

• Start at $(0,0)$.
• Sweep only columns $0$ to $n-2$ of each row, in snake order. Row $0$ runs from column $0$ toward column $n-2$, row $1$ runs from column $n-2$ toward column $0$, and the direction keeps alternating. At the end of a row, step straight down to the next row without changing the column, then sweep that row.
• After row $m-1$ is finished, move to $(m-1,n-1)$, then walk up column $n-1$ from $(m-1,n-1)$ to $(0,n-1)$.
• The last vertex $(0,n-1)$ is adjacent to $(0,0)$ through the wrap edge of row $0$, so the cycle closes.

Every toroidal grid with $3 \le m, n \le 100$ has such a cycle, so the first line of every test case is always 1.