시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB229840.000%

문제

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 < y_i$ and $A_{x_i} > 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!

입력

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$.

출력

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 < y_i \le n$), indicating the $i$-th operation $\text{swap}(A_{x_i},A_{y_i})$.

예제 입력 1

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

예제 출력 1

-1
2
1 2
2 4
7
7 8
6 7
5 6
4 5
3 4
2 3
1 2