分数: 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
我们不必执行该操作。