CF1491G.Switch and Flip

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.

有 $n$ 枚硬币，编号为 $1$ 到 $n$。初始时，位置 $i$ 上的硬币为 $c_i$，且所有硬币均正面朝上（其中 $(c_1, c_2, \dots, c_n)$ 是 $1$ 到 $n$ 的一个排列）。你可以对这些硬币执行若干操作。

每次操作可执行以下步骤：

• 选择两个不同的下标 $i$ 和 $j$；
• 交换位置 $i$ 和 $j$ 上的硬币；
• 翻转位置 $i$ 和 $j$ 上的硬币（若原本正面朝上，则翻转后变为反面朝上；反之亦然）。

请构造一个至多包含 $n+1$ 次操作的操作序列，使得执行完所有操作后，硬币 $i$ 恰好位于位置 $i$，且正面朝上。

注意：你无需最小化操作次数。

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$).

第一行包含一个整数 $n$（$3 \leq n \leq 2 \cdot 10^5$）—— 表示硬币的数量。

第二行包含 $n$ 个整数 $c_1,c_2,\dots,c_n$（$1 \le c_i \le n$，且当 $i\neq j$ 时，$c_i \neq c_j$）。

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.

第一行输出一个整数 $q$ $(0 \leq q \leq n+1)$ —— 表示你所使用的操作次数。

接下来的 $q$ 行中，每行输出两个整数 $i$ 和 $j$ $(1 \leq i, j \leq n, i \ne j)$ —— 表示当前操作所选择的位置。

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.

将正面朝上的第 $i$ 枚硬币记为 $i$，反面朝上的第 $i$ 枚硬币记为 $-i$。

第一个样例中执行的操作序列使硬币状态按如下方式变化：

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

在第二个样例中，硬币已处于正确位置，因此无需交换。