33OJ
登录 注册

#P17804. [ICPC 2019 Nanchang R] 9102

[ICPC 2019 Nanchang R] 9102

题目描述

众所周知,存在着无数代表不同世界的“世界线”。任何微小的改变都可能创造出一条新的世界线。

现在是公元 9102 年,人类已经在火星上生活了数千年,形成了许多部落。每个部落包含一个或多个家族。两个部落可以进行合并,其中一个部落中的所有家族都会迁往另一个部落;一个家族可能会灭绝,或者从其原来的部落迁徙到另一个家族所在的部落。

作为造物主,你统治着整个宇宙,因此你对火星上的一切都了如指掌。由于你经常忘记事情,你决定编写一个程序来管理这些正在发生的事情。

假设火星上有 nn 个部落,最初每个部落仅由一个家族构成。我们将这些部落以及这些家族从 11 到 nn 进行编号。你的程序需要支持以下五种类型的操作:

  • 1 k a b:将包含第 aa 个家族的部落与包含第 bb 个家族的部落合并;
  • 2 k a:使第 aa 个家族灭绝;
  • 3 k a b:第 aa 个家族离开其所在部落,加入包含第 bb 个家族的部落;
  • 4 k a b:报告第 aa 个家族与第 bb 个家族是否属于同一个部落;
  • 5 k a:报告包含第 aa 个家族的部落中的家族总数。

注意,对于每个带有参数 kk 的给定操作,你需要将自身置于第 kk 个操作之后的时间点的世界线中。

当你处理类型为 1 或 3 的操作时,第 aa 个家族与第 bb 个家族可能已经位于同一部落中,此时不会发生任何事情。同样地,给定的数字 aa 或 bb 可能指向一个已灭绝的家族,此时对于前三种类型的操作,不会发生任何事情;对于第四种类型的操作,应报告 No;对于第五种操作,应报告 0。

输入格式

第一行包含两个整数 nn 和 mm(1≤n,m≤10000001 \leq n, m \leq 1000000),分别表示初始的家族数量与操作数量。

接下来的 mm 行包含五种操作。第 ii 行包含三个或四个整数 opiop_i, kik_i, aia_i 和 bib_i(1≤opi≤51 \leq op_i \leq 5, 0≤ki≤i−10 \leq k_i \leq i-1, 1≤ai,bi≤n1 \leq a_i, b_i \leq n)。

输出格式

对于操作 4,你需要输出一行 Yes 或 No(不含引号);对于操作 5,你需要输出一行包含一个整数。

4 6 
1 0 1 2 
1 0 4 2 
3 2 4 3 
5 3 3 
2 1 1 
4 5 3 4
2
No

提示

:::align{center} :::

翻译由 DeepSeek V4 Pro 完成