SP3972 STARGATE - Stargates

「很久以前，在一个遥远的星系……」一个高度发达的文明发现了一种在恒星系统之间瞬间移动的方法。从那时起，他们专注于建造星门对，以连接不同的星球。然而，随着通信网络的扩展，他们管理这些信息变得越来越复杂，因此需要帮助来维持与世界连接相关的数据。 请编写一个程序，帮助他们维护连通系统的信息，我们会将你最优的解决方案推荐给他们的时空技术团队。 星球 $A$ 和星球 $B$ 是连通的，如果它们之间有直接的星门连接，或者存在一个星球序列 $P_1, P_2,\ldots, P_n$，使得 $P_1 = A$, $P_n = B$，并且对于每一个 $k \in \{2, \ldots, n\}$，$P_k$ 和 $P_{k-1}$ 之间都有直接的星门连接。 值得注意的是，这些连接是双向的。此外，两个星球之间可能存在多条连接路径。 ### 输入格式 输入文件包含多组数据。每组数据可能占据多行，且文件中没有空行。每行以一个字母 `D`、`C` 或 `Q`（不区分大小写）开头，接着是1到5个整数，具体含义如下： - `D N`：定义当前数据集中被考虑的星球总数为 $N$（$1 \leq N \leq 6000000$，星球编号从 1 到 $N$）。 - `C` 和 `Q` 命令后续的格式（以 `X` 表示）如下： - `X src dst`：创建或查询星球 `src` 和 `dst` 之间是否连通。 - `X src dst nnn`：创建或查询 `src` 星球与从 `dst` 开始的连续 `nnn` 个星球之间的连通性。 - `X src dst nnn step`：创建或查询 `src` 星球与从 `dst` 开始、第 `step` 个的 `nnn` 个星球之间的连通性。 - `X src dst nnn dststep srcstep`：创建或查询从 `src` 开始，每隔 `srcstep` 和从 `dst` 开始，每隔 `dststep` 的 `nnn` 对星球之间的连通性。 ### 输出格式 对于输入文件中的每一行查询（`Q`），输出包含一行结果。每行结果由两个空格分隔的数字构成。第一个数字表示查询中连通的星球对数量，第二个数字表示不连通的星球对数量。 ### 数据范围与提示 - 星球总数：$1 \leq N \leq 6000000$ - 星球编号：$1 \leq \text{src}, \text{dst} \leq N$ - 连续或步长的星球数量：$1 \leq \text{nnn} \leq 1000$ - 步长：$1 \leq \text{step} \leq 1000$ - 源目标步长：$1 \leq \text{srcstep}, \text{dststep} \leq 1000$ **本翻译由 AI 自动生成**

无

`

Output file contains one line pre each query (‘Q’) line in the input file. Each line contains two numbers

separated by a space. First value represents number of connected planet pairs from appropriate query while second

represents number of disconnected planet pairs.

`