CF1491G Switch and Flip

有 $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$ 的硬币，并且所有硬币正面朝上。 注意，你不需要最小化操作次数。

第一行包含一个整数 $n$（$3 \leq n \leq 2 \cdot 10^5$），表示硬币的数量。 第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \leq c_i \leq n$，对于 $i \neq j$ 有 $c_i \neq c_j$）。

第一行输出一个整数 $q$（$0 \leq q \leq n+1$），表示你使用的操作次数。 接下来的 $q$ 行，每行输出两个整数 $i$ 和 $j$（$1 \leq i, j \leq n, i \neq j$），表示本次操作选择的位置。

用 $i$ 表示编号为 $i$ 的硬币正面朝上，用 $-i$ 表示编号为 $i$ 的硬币反面朝上。 第一个样例中操作后的硬币变化如下： - $[~~~2,~~~1,~~~3]$ - $[-3,~~~1,-2]$ - $[-3,~~~2,-1]$ - $[~~~1,~~~2,~~~3]$ 第二个样例中，硬币已经在正确的位置上，因此不需要进行任何操作。 由 ChatGPT 4.1 翻译