408988: GYM103409 D 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.

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

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
2
1 2
2 4
7
7 8
6 7
5 6
4 5
3 4
2 3
1 2