← 返回题目列表

Codeforces · 22/E

E. 方案

中文机器翻译题面 查看原题

为了尽快了解他们最喜欢的全新操作系统的最新消息,来自 Nizhni Tagil 的 BolgenOS 社区决定开发一个计划。根据该方案,第一个获悉该消息的社区成员呼叫其他成员,后者依次呼叫第三个成员,依此类推;即,一个具有索引的人,我找到了一个具有索引 fi 的人,如果他得知这个消息,他必须给他打电话。随着时间的推移,BolgenOS 社区成员明白他们的计划有时行不通——在某些情况下,一些成员根本不知道这个消息。现在他们想要补充该方案:他们在方案中添加一些类型为(xi,yi)的指令,这意味着人 xi 也必须呼叫人 yi。他们需要添加的最少指令是多少,以便最终每个人都能获悉该消息,无论谁是第一个获悉该消息的?

输入

第一输入行包含数字 n (2 ≤ n ≤ 105) — BolgenOS 社区成员的数量。第二行包含 n 个空格分隔的整数 fi (1 ≤ fi ≤ n, i ≠ fi) — 一个人的索引,向该人呼叫索引为 i 的人。

输出

在第一行输出一个数字——要添加的最小指令量。然后输出可能的变体之一,将这些指令添加到方案中,每行一条指令。如果解不唯一,则输出任意一个。

示例

输入 #1

3
3 3 2

输出 #1

1
3 1

输入 #2

7
2 3 1 3 4 4 1

输出 #2

3
2 5
2 6
3 7