Switch and Flip
Contest: Codeforces Global Round 13
Difficulty rating: 2800
Tags: constructive algorithms, graphs, math

There are $$$n$$$ coins labeled from $$$1$$$ to $$$n$$$. Initially, coin $$$c_i$$$ is on position $$$i$$$ and is facing upwards (($$$c_1, c_2, \dots, c_n)$$$ is a permutation of numbers from $$$1$$$ to $$$n$$$). You can do some operations on these coins.

In one operation, you can do the following:

- Choose $$$2$$$ distinct indices $$$i$$$ and $$$j$$$.
- Then, swap the coins on positions $$$i$$$ and $$$j$$$.
- Then, flip both coins on positions $$$i$$$ and $$$j$$$. (If they are initially faced up, they will be faced down after the operation and vice versa)

Construct a sequence of at most $$$n+1$$$ operations such that after performing all these operations the coin $$$i$$$ will be on position $$$i$$$ at the end, facing up.

Note that you do not need to minimize the number of operations.

Input format:
The first line contains an integer $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — the number of coins.

The second line contains $$$n$$$ integers $$$c_1,c_2,\dots,c_n$$$ ($$$1 \le c_i \le n$$$, $$$c_i \neq c_j$$$ for $$$i\neq j$$$).

Output format:
In the first line, output an integer $$$q$$$ $$$(0 \leq q \leq n+1)$$$ — the number of operations you used.

In the following $$$q$$$ lines, output two integers $$$i$$$ and $$$j$$$ $$$(1 \leq i, j \leq n, i \ne j)$$$ — the positions you chose for the current operation.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Let coin $$$i$$$ facing upwards be denoted as $$$i$$$ and coin $$$i$$$ facing downwards be denoted as $$$-i$$$.

The series of moves performed in the first sample changes the coins as such:

- $$$[~~~2,~~~1,~~~3]$$$
- $$$[-3,~~~1,-2]$$$
- $$$[-3,~~~2,-1]$$$
- $$$[~~~1,~~~2,~~~3]$$$

In the second sample, the coins are already in their correct positions so there is no need to swap.

Example input:
3
2 1 3

Example output:
3
1 3
3 2
3 1

Example input:
5
1 2 3 4 5

Example output:
0

Editorial:
We can visualize the problem as a graph with nodes of $$$2$$$ colors (face up — red and face down — blue). Initially, the graph has nodes with all red color and with a directed edge to $$$c_i$$$.
Firstly, any $$$2$$$ cycles with all red nodes can be converted into a single cycle with $$$2$$$ blues nodes with $$$1$$$ swap.
A cycle with $$$2$$$ blue nodes is very convenient here as swapping a blue node with a red node it is pointing to will decrease the cycle size and maintain that the cycle still has $$$2$$$ blue nodes. We can keep decreasing the cycle size until the cycle has only $$$2$$$ blue nodes and solve that in $$$1$$$ swap. Thus, solving $$$2$$$ cycles which have $$$X$$$ nodes in total uses only $$$X$$$ swaps.
Now, we simply pair the cycles and do this.
However, if there is an odd number of cycles, there are $$$2$$$ cases:
If the cycle does not cover the whole graph, we can solve the remaining cycle and a cycle of size $$$1$$$ together.
Otherwise, we can force $$$2$$$ blue nodes into the cycle with $$$2$$$ swaps (does not work for $$$n = 2$$$ so be careful).
Both cases need $$$X+1$$$ moves where $$$X$$$ is the size of the remaining cycle.
Thus, at most $$$X+1$$$ swaps is needed in this algorithm.