Permutation Factory
Contest: Ethflow Round 1 (Codeforces Round 1001, Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: flows, geometry, graph matchings, graphs

You are given two permutations $$$p_1,p_2,\ldots,p_n$$$ and $$$q_1,q_2,\ldots,q_n$$$ of length $$$n$$$. In one operation, you can select two integers $$$1\leq i,j\leq n,i\neq j$$$ and swap $$$p_i$$$ and $$$p_j$$$. The cost of the operation is $$$\min (|i-j|,|p_i-p_j|)$$$.

Find the minimum cost to make $$$p_i = q_i$$$ hold for all $$$1\leq i\leq n$$$ and output a sequence of operations to achieve the minimum cost.

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 format:
The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of input test cases.

The first line of each test case contains one integer $$$n$$$ ($$$2 \le n \le 100$$$) — the length of permutations $$$p$$$ and $$$q$$$.

The second line contains $$$n$$$ integers $$$p_1,p_2,\ldots,p_n$$$ ($$$1\leq p_i\leq n$$$) — the permutation $$$p$$$. It is guaranteed that $$$p_1,p_2,\ldots,p_n$$$ is a permutation of $$$1,2,\ldots,n$$$.

The third line contains $$$n$$$ integers $$$q_1,q_2,\ldots,q_n$$$ ($$$1\leq q_i\leq n$$$) — the permutation $$$q$$$. It is guaranteed that $$$q_1,q_2,\ldots,q_n$$$ is a permutation of $$$1,2,\ldots,n$$$.

It is guaranteed that the sum of $$$n^3$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, output the total number of operations $$$k$$$ ($$$0\le k\le n^2$$$) on the first line. Then output $$$k$$$ lines, each containing two integers $$$i,j$$$ ($$$1\le i,j\le n$$$, $$$i\neq j$$$) representing an operation to swap $$$p_i$$$ and $$$p_j$$$ in order.

It can be shown that no optimal operation sequence has a length greater than $$$n^2$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the second test case, you can swap $$$p_1,p_3$$$ costing $$$\min(|1-3|,|1-3|)=2$$$. Then $$$p$$$ equals $$$q$$$ with a cost of $$$2$$$.

In the third test case, you can perform the following operations:

Initially, $$$p=[2,1,4,3]$$$.

1. Swap $$$p_1,p_4$$$ costing $$$\min(|1-4|,|2-3|)=1$$$, resulting in $$$p=[3,1,4,2]$$$.
2. Swap $$$p_2,p_4$$$ costing $$$\min(|2-4|,|1-2|)=1$$$, resulting in $$$p=[3,2,4,1]$$$.
3. Swap $$$p_1,p_3$$$ costing $$$\min(|1-3|,|3-4|)=1$$$. Then $$$p$$$ equals $$$q$$$ with a cost of $$$3$$$.

Example input:
4
2
2 1
2 1
3
1 2 3
3 2 1
4
2 1 4 3
4 2 3 1
5
1 4 3 2 5
5 2 3 4 1

Example output:
0
1
1 3
3
1 4
2 4
1 3
4
1 2
4 5
2 5
1 4

Editorial:
Because the cost of an operation is $$$\min(|i-j|,|p_i-p_j|)$$$, we can consider this operation as two operations with different costs, one costing $$$|i-j|$$$ and the other costing $$$|p_i-p_j|$$$.
Consider each number in the permutation as a point $$$(i, p_i)$$$ on a two-dimensional plane. So the first operation can be seen as moving $$$(i, p_i)$$$ to $$$(i, p_j)$$$, and simultaneously moving $$$(j, p_j)$$$ to $$$(j, p_i)$$$. The second operation can be seen as moving $$$(i, p_i)$$$ to $$$(j, p_i)$$$ and simultaneously moving $$$(j, p_j)$$$ to $$$(i, p_j)$$$. The cost of both modes of movement is the coordinate distance between these two points.
Supposing that the restriction that two points should be moved simultaneously is removed. Meanwhile, divide the cost of one operation equally between the movements of two points. Then, the cost of moving a point from one coordinate to another is the Manhattan distance between these two points divided by $$$2$$$, and the minimum cost is the minimum cost matching to move each point of $$$p$$$ to match each point of $$$q$$$.
Next, we will prove that the minimum answer obtained after removing the simultaneous movement restriction can always be obtained under restricted conditions.
First, find any minimum cost matching between points of $$$p$$$ and points of $$$q$$$. Assume that point $$$(i,p_i)$$$ matches point $$$(a_i,q_{a_i})$$$, where $$$a$$$ is also a permutation. We first make point moves parallel to the x-axis direction. If there exists $$$a_i \neq i$$$, find the $$$i$$$ with the smallest $$$a_i$$$ among them. Then, there must exist $$$j$$$ where $$$a_i \le j < i \le a_j$$$. By performing such operations on $$$i$$$ and $$$j$$$, these two points can be moved without increasing the total cost. Continuously performing this operation can complete the movement of all points in the x-axis direction. The same applies to the movement in the y-axis direction.
Using the minimum cost and maximum flow to find the minimum cost matching and checking every pair of $$$(i,j)$$$ to find a swappable pair will result in a solution with $$$O(n^4)$$$ time complexity. Using the Kuhn-Munkres Algorithm to find the minimum cost matching, checking only $$$a_i$$$ mentioned above can achieve a time complexity of $$$O (n^3)$$$, but is not required.