Lesson 3

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

• Input format.  The first line contains the integer \(n\) (\(2 \le n \le 1000\)). 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 n\) — the number of transpositions used. The next \(t\) lines should contain the descriptions of the transpositions as two different indices from \(0\) to \(n\), separated by a space.

3
3 0 2 1
0 1 2 3

2
0 1
1 3