← 返回题目列表

Codeforces · 755/C

C. 波兰球和森林

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

波兰鲍尔和他的家人住在森林里。森林里有一些树。树是具有 k 个顶点和 k - 1 个边的无向无环图,其中 k 是某个整数。请注意,一个顶点是一棵有效的树。

每棵树的每个顶点都有一个亲戚,他们有从 1 到 n 的唯一 id。对于每个球 i,我们知道住在同一棵树上的最远亲的 ID。如果有多个这样的顶点,我们只知道其中 id 最小的那个的值。

森林里有多少棵树?

输入

第一行包含单个整数 n (1 ≤ n ≤ 104) — 生活在森林中的球的数量。

第二行包含长度为 n 的序列 p1, p2, ..., pn,其中 (1 ≤ pi ≤ n) 成立,pi 表示与生活在同一棵树上的 Ball i 最远的亲戚。如果有几个最远的亲戚住在同一棵树上,pi 就是 id 最小的一个的 id。

保证序列 p 对应于某个有效的森林。

黑客攻击:要黑客攻击某人,您应该提供正确的森林作为测试。序列 p 将根据森林进行计算,并将其提供给您尝试破解的解决方案作为输入。使用以下格式:

在第一行中,输出整数 n (1 ≤ n ≤ 104) — 球的数量和整数 m (0 ≤ m < n) — 森林中的边总数。然后应该有 m 行。其中第 i 个应该包含两个整数 ai 和 bi 并表示 ai 和 bi 相关的顶点之间的边。例如第一个样例的写法如下:

互动

从技术角度来看,这个问题是交互式的。但是,它不应该影响您(黑客攻击除外),因为没有交互。

输出

您应该输出PolandBall居住的森林中的树木数量。

示例

输入 #1

5
2 1 5 3 3

输出 #1

2

输入 #2

1
1

输出 #2

1

注意

在第一个示例测试用例中,可能的森林是:1-2 3-4-5。

总共有 2 棵树。

在第二个示例测试用例中,唯一可能的图是一个顶点且没有边。因此,只有一棵树。