C. You Soared Afar With Grace
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a permutation $$$a$$$ and $$$b$$$ of length $$$n$$$$$$^{\text{∗}}$$$. You can perform the following operation at most $$$n$$$ times:

  • Choose two indices $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$, $$$i \ne j$$$), swap $$$a_i$$$ with $$$a_j$$$, swap $$$b_i$$$ with $$$b_j$$$.

Determine whether $$$a$$$ and $$$b$$$ can be reverses of each other after operations. In other words, for each $$$i = 1, 2, \ldots, n$$$, $$$a_i = b_{n + 1 - i}$$$.

If it is possible, output any valid sequence of operations. Otherwise, output $$$-1$$$.

$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ 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 ($$$n=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 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the length of the permutations.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$).

The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$).

It is guaranteed that $$$a$$$ and $$$b$$$ are permutations of length $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, if it is impossible, output $$$-1$$$ in the only line. Otherwise, output a single integer $$$m$$$ ($$$0 \le m \le n$$$) — the number of operations in the first line. In the following $$$m$$$ lines, output two integers — the indices $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$, $$$i \ne j$$$) in each operation in order. If there are multiple solutions, print any of them.

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

In the second test case, $$$b$$$ is already the reverse of $$$a$$$.

In the third test case, after performing the following operation, $$$b$$$ will become the reverse of $$$a$$$:

  • Swap $$$a_1, a_2$$$ and swap $$$b_1, b_2$$$. Now $$$a = [3, 1, 2, 4]$$$ and $$$b = [4, 2, 1, 3]$$$.

In the fourth test case, after performing the following operations in order, $$$b$$$ will become the reverse of $$$a$$$:

  • Swap $$$a_1, a_2$$$ and swap $$$b_1, b_2$$$. Now $$$a = [5, 2, 1, 3, 4]$$$ and $$$b = [5, 3, 4, 2, 1]$$$.
  • Swap $$$a_1, a_3$$$ and swap $$$b_1, b_3$$$. Now $$$a = [1, 2, 5, 3, 4]$$$ and $$$b = [4, 3, 5, 2, 1]$$$.