Switch and Flip

题意翻译

桌面上有 $n$ 枚硬币。初始时,第 $c_i$ 号硬币位于位置 $i$,正面朝上($c_1, c_2, \cdots, c_n$ 是一个 $1 \sim n$ 的排列)。你可以对这些硬币做一些操作。每次操作,你可以如下进行: * 选择两个不同的 $i$ 和 $j$。 * 交换位于 $i$ 和 $j$ 的两枚硬币。 * 把位于 $i$ 和 $j$ 的两枚硬币分别翻转。 你可以进行不超过 $n + 1$ 次操作,使得第 $i$ 号硬币位于位置 $i$,且都是正面朝上。 你**不需要**最小化操作的次数,输出任意一种方案即可。

题目描述

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.

输入输出格式

输入格式


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

输出格式


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.

输入输出样例

输入样例 #1

3
2 1 3

输出样例 #1

3
1 3
3 2
3 1

输入样例 #2

5
1 2 3 4 5

输出样例 #2

0

说明

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.