P17804 [ICPC 2019 Nanchang R] 9102

众所周知，存在着无数代表不同世界的“世界线”。任何微小的改变都可能创造出一条新的世界线。 现在是公元 9102 年，人类已经在火星上生活了数千年，形成了许多部落。每个部落包含一个或多个家族。两个部落可以进行合并，其中一个部落中的所有家族都会迁往另一个部落；一个家族可能会灭绝，或者从其原来的部落迁徙到另一个家族所在的部落。 作为造物主，你统治着整个宇宙，因此你对火星上的一切都了如指掌。由于你经常忘记事情，你决定编写一个程序来管理这些正在发生的事情。 假设火星上有 $n$ 个部落，最初每个部落仅由一个家族构成。我们将这些部落以及这些家族从 $1$ 到 $n$ 进行编号。你的程序需要支持以下五种类型的操作： - `1 k a b`：将包含第 $a$ 个家族的部落与包含第 $b$ 个家族的部落合并； - `2 k a`：使第 $a$ 个家族灭绝； - `3 k a b`：第 $a$ 个家族离开其所在部落，加入包含第 $b$ 个家族的部落； - `4 k a b`：报告第 $a$ 个家族与第 $b$ 个家族是否属于同一个部落； - `5 k a`：报告包含第 $a$ 个家族的部落中的家族总数。 注意，对于每个带有参数 $k$ 的给定操作，你需要将自身置于第 $k$ 个操作**之后**的时间点的世界线中。 当你处理类型为 1 或 3 的操作时，第 $a$ 个家族与第 $b$ 个家族可能已经位于同一部落中，此时不会发生任何事情。同样地，给定的数字 $a$ 或 $b$ 可能指向一个已灭绝的家族，此时对于前三种类型的操作，不会发生任何事情；对于第四种类型的操作，应报告 `No`；对于第五种操作，应报告 `0`。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 1000000$），分别表示初始的家族数量与操作数量。 接下来的 $m$ 行包含五种操作。第 $i$ 行包含三个或四个整数 $op_i$, $k_i$, $a_i$ 和 $b_i$（$1 \leq op_i \leq 5$, $0 \leq k_i \leq i-1$, $1 \leq a_i, b_i \leq n$）。

对于操作 4，你需要输出一行 `Yes` 或 `No`（不含引号）；对于操作 5，你需要输出一行包含一个整数。

:::align{center}  ::: 翻译由 DeepSeek V4 Pro 完成