D. Assumption is All You Need
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

JB holds the belief that assumption is all you need to solve a problem. In order to prove that, JB has given you two permutations of numbers from $$$1$$$ to $$$n$$$: $$$A$$$ and $$$B$$$, and JB wants you to output a sequence of element swapping operation $$$(x_i,y_i)$$$ on $$$A$$$, so that:

  1. every pair of swapped element forms an inversion pair (i.e. $$$x_i \lt y_i$$$ and $$$A_{x_i} \gt A_{y_i}$$$ when the $$$i$$$-th operation is being performed)
  2. $$$A$$$ will become $$$B$$$ at the end of the swapping sequence.
or determine it is impossible. Help prove JB's belief by solving this problem!
Input

There are multiple test cases. The first line of the input contains one integer $$$T$$$ indicating the number of test cases. For each test case:

The first line contains one integer $$$n$$$ ($$$1 \le n \le 2\,021$$$), indicating the number elements in $$$A$$$ and $$$B$$$.

The second line contains $$$n$$$ distinct integers $$$A_1,A_2,\dots,A_n$$$ ($$$1 \le A_i \le n$$$), indicating the array $$$A$$$.

The third line contains $$$n$$$ distinct integers $$$B_1,B_2,\dots,B_n$$$ ($$$1 \le B_i \le n$$$), indicating the array $$$B$$$.

It is guaranteed that the sum of $$$n$$$ in all test cases will not exceed $$$2\,021$$$.

Output

For each test case, if there doesn't exist a sequence, output the one line containing one integer "-1".

Otherwise, in the first line output one integer $$$k$$$ ($$$0 \le k \le \frac{n(n-1)}{2}$$$), indicating the length of the swapping sequence. Then, output $$$k$$$ line each containing two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i \lt y_i \le n$$$), indicating the $$$i$$$-th operation $$$\text{swap}(A_{x_i},A_{y_i})$$$.

Example
Input
3
2
1 2
2 1
4
4 1 2 3
1 3 2 4
8
8 7 6 5 4 3 2 1
1 8 7 6 5 4 3 2
Output
-1
2
1 2
2 4
7
7 8
6 7
5 6
4 5
3 4
2 3
1 2