Number Connection Puzzle

In a grid of numbers, two cells with the same number must be connected by one line. In this problem, exactly two cells contain the number 1.

The line moves only between horizontally or vertically adjacent cells. It cannot break, branch, or cross itself. The two 1 cells must be the two endpoints of the line, and the line must pass through every cell of the grid exactly once.

The number of rows m and columns n are both even, and 2 ≤ m, n ≤ 8. Given the positions of the two 1 cells, find a path that satisfies these conditions.

The first line contains the number of test cases T.

For each test case, the first line contains the number of rows m and columns n. The next two lines contain the positions (i, j) and (a, b) of the two 1 cells. All coordinates are 1-indexed.

For each test case, print -1 if no valid path exists.

Otherwise, print 1 first, followed by m × n lines containing the coordinates visited by the path in order. The first and last coordinates must be the two given 1 cells.