Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4018
Crosses Puzzles

Time Limit: 1 Second      Memory Limit: 65536 KB      Special Judge

Given a grid with \(n\) rows and \(m\) columns, each cell may contain nothing or a cross consisting of three dotted segments and one solid segment. Let's denote the cell located on the \(i\)-th row and the \(j\)-th column by \((i, j)\).

When you click on a cross, it will rotate 90 degrees clockwise, thus changing the direction the solid segment points to. Your goal is to click on some crosses in some proper order so that the solid segment of every cross points upwards.

But beware, this task is harder than you think it may be. After the rotation of a cross in \((i,j)\) ends, the cross \((i',j')\) pointed by the solid segment of \((i,j)\) will also begin to rotate 90 degrees clockwise, and after the rotation of \((i',j')\) ends, another cross may be triggered if pointed by the solid segment of \((i',j')\)... This chain reaction comes to an end only when the solid segment of the previously-rotated cross points to an empty cell or points out of the map.

To help you understand, please check the following pictures showing a chain reaction on a grid with \(n = m = 3\) step by step.

This is the initial state before the chain reaction.
Now let's click on the cross (1, 1).

After clicking, (1, 1) rotates 90 degrees clockwise
and its solid segment points to (1, 2).

(1, 2) is activated and rotates 90 degrees clockwise.
After rotation, its solid segment points to (1, 3).

(1, 3) is activated and rotates 90 degrees clockwise.
After rotation, its solid segment points back to (1, 2).

(1, 2) is activated again and rotates.
After rotation, its solid segment points to (2, 2).

(2, 2) is activated and rotates 90 degrees clockwise.
After rotation, its solid segment points to (2, 3).

As (2, 3) is an empty cell,
the chain reaction stops.

Given a grid with \(n\) rows and \(m\) columns, please find out a proper order to click on the crosses so that the solid segment of every cross points upwards. You can perform at most 6000 clicks for each test case.

Input

There are multiple test cases. The first line of the input contains an integer \(T\) (\(1 \le T \le 50\)), indicating the number of test cases. For each test case:

The first line contains two integers \(n\) and \(m\) (\(1 \le n, m \le 10\)), indicating the size of the grid.

For the following \(n\) lines, the \(i\)-th line contains \(m\) integers \(t_{i,1}, t_{i,2}, \dots, t_{i,m}\) (\(-1 \le t_{i,j} \le 3\)), where \(t_{i,j}\) indicates the initial state of the cross at intersection \((i, j)\).

  • If \(t_{i,j} = 0\), the solid segment of the cross in cell \((i,j)\) is initially pointing upwards.
  • If \(t_{i,j} = 1\), the solid segment of the cross in cell \((i,j)\) is initially pointing leftwards.
  • If \(t_{i,j} = 2\), the solid segment of the cross in cell \((i,j)\) is initially pointing downwards.
  • If \(t_{i,j} = 3\), the solid segment of the cross in cell \((i,j)\) is initially pointing rightwards.
  • If \(t_{i,j} = -1\), cell \((i,j)\) is an empty cell.

Output

For each test case, first output one line containing one integer \(k\) (\(0 \le k \le 6000\)), indicating the number of clicks. Then \(k\) lines follow. Each line contains two integers \(i, j\) (\(1 \le i \le n, 1 \le j \le m\)) separated by a space, indicating that you click on the cross in cell \((i, j)\).

If there's no way to make the solid segment of every cross point upwards in 6000 clicks, just output "-1" (without quotes) instead.

Sample Input

2
3 2
2 3
-1 0
3 2
2 2
3 2
0 1

Sample Output

8
1 1
1 2
1 2
2 2
2 2
3 1
3 1
3 2
5
1 1
2 1
2 1
2 1
1 2

Hint

We've also prepared the following playable example with \(n = m = 4\). You can try it for further understanding.

(If you cannot see this example, try Firefox)

(Controls: Click to rotate, and refresh to restart)


Author: YANG, Xinyu
Source: The 18th Zhejiang University Programming Contest Sponsored by TuSimple
Submit    Status