31137번 - Assumption is All You Need 스페셜 저지다국어

문제

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

제한

힌트