← 返回题目列表

AtCoder · arc097_b

D. 等于

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

分数: 400 点

问题陈述

我们有以下整数的排列 1 通过 N, p_1, p_2, .., p_N。 我们还有 M 之间的两个整数对 1 和 N (含),表示为 (x_1,y_1), (x_2,y_2), .., (x_M,y_M)。 AtCoDeer 鹿将执行以下操作 p 根据需要多次,以便 i (1 ≤ i ≤ N) 这样 p_i = i 最大化:

  • 选择 j 这样 1 ≤ j ≤ M,并交换 p_{x_j} 和 p_{y_j}.

找出最大可能的数量 i 这样 p_i = i 操作后。

约束

  • 2 ≤ N ≤ 10^5
  • 1 ≤ M ≤ 10^5
  • p 是以下整数的排列 1 通过 N.
  • 1 ≤ x_j,y_j ≤ N
  • x_j ≠ y_j
  • If i ≠ j, \{x_i,y_i\} ≠ \{x_j,y_j\}.
  • 输入中的所有值都是整数。 您选择的

输入

输入由标准输入按以下格式给出:

N M
p_1 p_2 .. p_N
x_1 y_1
x_2 y_2
:
x_M y_M

输出

打印最大可能数量 i 这样 p_i = i 操作后。


示例输入 1

5 2
5 3 1 4 2
1 3
5 4

示例输出 1

2

如果我们通过选择执行操作 j=1, p 变为 1 3 5 4 2,这是最优的,所以答案是 2.


示例输入 2

3 2
3 2 1
1 2
2 3

示例输出 2

3

如果我们执行操作,例如,选择 j=1, j=2, j=1 按此顺序, p 变为 1 2 3,这显然是最佳的。 请注意,我们可以选择相同的 j 任意次数。


示例输入 3

10 8
5 3 6 8 7 10 9 1 2 4
3 1
4 1
5 9
2 5
6 5
3 5
8 9
7 9

示例输出 3

8

示例输入 4

5 1
1 2 3 4 5
1 5

示例输出 4

5

我们不必执行该操作。