Lesson 7

Programming problem. Given two permutations of \(\{0, \dotsc, n\}\), transform the first permutation into the second one using at most \(2(n+1)^{2}\) neighbor transpositions.

• Input format.  The first line contains the integer \(n\) (\(2 \le n \le 100\)). The next two lines contain \(n+1\) integers separated by spaces — the elements of the permutations. It is guaranteed that each of these lines defines a valid permutation, that is, \(\pi[i] \ne \pi[j]\) for \(i \ne j\) and \(0 \le \pi[i] \le n\).


• Output format.  The first line of the output should contain one integer \(t\) such that \(0 \le t \le 2(n+1)^{2}\) — the number of transpositions used. The next \(t\) lines should contain the descriptions of neighbor transpositions as two different indices from \(0\) to \(n\), separated by a space, whose difference is one.

3
3 0 2 1
0 1 2 3

4
0 1
1 2
2 3
1 2