#P5584. Colored Ball

    ID: 4585 传统题 1000ms 512MiB 尝试: 22 已通过: 10 难度: 4 上传者: 标签>CF1600普及+/提高-小并大合并集合有序集合树论启发式合并

Colored Ball

题面翻译

给定 NN 个盒子,每个盒子里面有一个颜色为 CiC_i 的小球。有 QQ 次操作,每次操作将第 aia_i 个盒子中的球都放到第 bib_i 个盒子里面,你需要在每次操作后输出当前操作结束后第 bib_i 个盒子里面有多少个不同颜色的小球。

如果盒子为空,输出 00 即可。

样例 #1

样例输入 #1

6 5
1 1 1 2 2 3
1 2
6 4
5 1
3 6
4 6

样例输出 #1

1
2
1
1
3

样例 #2

样例输入 #2

5 3
2 4 2 4 2
3 1
2 5
3 2

样例输出 #2

1
2
0

提示

制約

  • 1 ≤ N, Q ≤ 200000 1\ \leq\ N,\ Q\ \leq\ 200000
  • 1 ≤ Ci ≤ N 1\ \leq\ C_i\ \leq\ N
  • 1 ≤ a, b ≤ N 1\ \leq\ a,\ b\ \leq\ N
  • a ≠ b a\ \neq\ b