P8210 [THUPC 2022 Preliminary] Building a Computer

After hearing that your department has a course on building a computer, Little R and Little C were so scared that they submitted withdrawal applications overnight. Just kidding. As freshmen, they are not afraid of this course at all; they even find it a bit funny. Their strong hands-on ability even pushes them to build something just for fun. Of course, since they are only freshmen and have basically taken no CS major courses, after a long and tough struggle, they finally built a strange device: This computer has only $n$ memory cells, but it has sufficiently many registers. The memory cells are numbered from $1$ to $n$, and the registers are numbered starting from $n+1$ upwards. Each memory cell and each register can store one integer. They have currently designed one type of instruction: `swap i, j`, which means swapping the numbers stored in the two positions numbered $i$ and $j$, where $i$ and $j$ are both positive integers and $i \neq j$. They plan to write a program to test this instruction. At the beginning, the $n$ memory cells contain the numbers $1\thicksim n$ in a random order, and each number appears exactly once. In each register, the stored value equals its own index. They want to design a sequence of instructions such that after the computer executes all of them in order, all numbers in both memory cells and registers are in the correct places, meaning each position contains exactly its own index. Although they have not studied CS courses, Little R and Little C still know a little, so they require that in each `swap` instruction, at least one of the two positions must be a register; that is, at least one of $i$ and $j$ should be greater than $n$. However, just as they finished writing the program and started running it, the system crashed. After searching for the cause for a long time, they found a strange bug: the computer they built cannot execute two identical instructions. In other words, they cannot have two identical `swap i, j` instructions in the same program. Moreover, they found that even having one `swap i, j` and one `swap j, i` is also not allowed, because the computer will automatically treat them as the same instruction. Little R and Little C were devastated. But before giving up, they still plan to write the program using the existing architecture. Not only that, they also want to use as few registers as possible. Can you help them?

The first line contains a positive integer $n\ (1 \leq n \leq 10^5)$, representing the number of memory cells. The second line contains $n$ positive integers $a_i$, where $a_i$ is the initial value in the $i$-th memory cell. It is guaranteed that all $a_i$ form a permutation of $1 \thicksim n$.

The first line contains two non-negative integers $m,k$, representing the number of registers you use and the number of instructions, respectively. In the next $k$ lines, output two positive integers $i, j$ per line, representing the two positions swapped in each instruction you design, in order. You need to ensure that $1 \leq i,j \leq n+m$, and that all instruction constraints in the statement are satisfied. If there are multiple valid instruction sequences, output any one of them. You need to minimize $m$ but do not need to minimize $k$. However, you must ensure that $k \leq 10^6$. The input guarantees that a solution satisfying the requirements exists.

[Sample Explanation] Initially, the values in the first $4$ cells are $(2,1,3,4)$. Execute `swap 3, 4`, and the values become $(2,1,4,3)$. Execute `swap 1, 3`, and the values become $(4,1,2,3)$. Execute `swap 2, 4`, and the values become $(4,3,2,1)$. Execute `swap 1, 4`, and the values become $(1,3,2,4)$. Execute `swap 2, 3`, and the values become $(1,2,3,4)$. It can be proven that $m=1$ is impossible. Translated by ChatGPT 5