Easy NPC Problem

It is preferrable to read the pdf statment.

Cuber QQ fell in love with research of NPC problem. He is very passionate in those cutting-edge thinkings, especially in Hamiltonian path problem, which is a well-known typical NPC problem.

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. Mathematicians have spent hundreds of years, trying to find a general yet elegant solution of this problem, but still, the problem is only solved in a limited scope.

Cuber QQ wants to take one step forward, by solving the Hamiltonian path problem in the grid. A grid has $n \times m$ vertices. We use a typical coordinate system in the grid, where each vertex on the grid is labelled by a pair of integers $(x, y)$ $(1 \le x \le n, 1 \le y \le m)$, and it is connected to adjacent vertices (if they are available), i.e., $(x-1, y)$, $(x+1, y)$, $(x, y-1)$, $(x, y+1)$.

The problem seems too trivial to him, Cuber QQ will take another step forward to find a Hamiltonian path in the grid without visiting the vertex $(N_x,N_y)$ $(1 \le N_x \le n, 1 \le N_y \le m)$, and the starting vertex must be located at $(S_x,S_y)$ $(1 \le S_x \le n, 1 \le S_y \le m)$. It is a little too difficult for him now and he asks you for help.

The first line contains an integer $T$ ($T \le 2~500$), denoting the number of test cases.

Each test case has six space-separated integers $n,m,N_x,N_y,S_x,S_y$ ($1\le N_x,S_x\le n \le 200$, $1\le N_y, S_y\le m \le 200$, $N_x\neq S_x$ or $N_y \neq S_y$) in one line.

It is guaranteed that $\sum n+m\le 10^5$.

For each test case, if there is no solution, print a single integer $-1$ in one line, otherwise the first line output an integer $nm - 1$, which is the length of the path. The next $nm - 1$ lines contain the vertices in the visiting order. and each of the $n$ lines contains two space-separated integers $x,y$ ($1 \le x \le n, 1 \le y \le m$).

If there are multiple solutions, print any.

2
2 4 1 2 1 1
2 4 2 2 1 1

7
1 1
2 1
2 2
2 3
2 4
1 4
1 3
-1

2020 Multi-University Training Contest 8