F. Deglado
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a $$$2n \times 2n$$$ grid $$$a$$$ where each column is a permutation$$$^{\text{∗}}$$$ of length $$$2n$$$.

We want to sort all columns in ascending order from top to bottom by performing the following operation:

  • Choose a $$$2 \times 2$$$ subgrid and swap the two top elements with the two bottom elements.

    More formally, you can choose two integers $$$i$$$ and $$$j$$$ ($$$1 \leq i, j \lt 2n$$$), then swap $$$a_{i,j}$$$ with $$$a_{i+1,j}$$$ and swap $$$a_{i,j+1}$$$ with $$$a_{i+1,j+1}$$$.

You have to sort all columns using at most $$$n \cdot \binom{2n}{2} + 9n$$$ operations, or determine that it is impossible.

Note that you do not need to minimize the number of operations.

$$$^{\text{∗}}$$$A permutation of length $$$m$$$ is an array consisting of $$$m$$$ distinct integers from $$$1$$$ to $$$m$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$m=3$$$ but there is $$$4$$$ in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

The first line of each test contains a single integer $$$n$$$ ($$$1 \leq n \leq 80$$$).

The $$$i$$$-th line of the next $$$2n$$$ lines contains $$$2n$$$ integers $$$a_{i,1},a_{i,2},\ldots,a_{i,2n}$$$ ($$$1 \leq a_{i,j} \leq 2n$$$) — the elements of the $$$i$$$-th row of the grid.

It is guaranteed that every column in the grid forms a permutation of length $$$2n$$$.

It is guaranteed that the sum of $$$n^3$$$ over all test cases does not exceed $$$80^3$$$.

Output

For each test case, if it is impossible to sort all columns in at most $$$n \cdot \binom{2n}{2} + 9n$$$ operations, print $$$-1$$$ in a single line.

Otherwise, in the first line print a single integer $$$k$$$ ($$$0 \leq k \leq n \cdot \binom{2n}{2} + 9n$$$) — the number of operations.

Then $$$k$$$ lines follow, the $$$w$$$-th line containing two integers $$$i_w$$$ and $$$j_w$$$ ($$$1 \leq i_w, j_w \lt 2n$$$) — you choose $$$i_w$$$ and $$$j_w$$$ in the $$$w$$$-th operation.

Example
Input
3
1
2 2
1 1
1
1 2
2 1
2
1 2 2 1
2 1 3 3
4 4 1 2
3 3 4 4
Output
1
1 1
-1
3
3 1
2 3
1 2
Note

In the first test case, you can sort columns using one operation.

In the second test case, it can be shown that you cannot sort columns.

The illustration of the third test case: