题目描述

译自 JOI Open 2018 T3 「崖崩れ / Collapse」

在 JOI 国有 $N$​​ 个城镇，它们坐落于一个幽深峡谷中。城镇按到海洋的距离的顺序分别编号为 $0,1,\ldots ,N-1$。

I 先生是 JOI 国科学委员会的主席，他准备维护城镇之间双向连接的电缆。目前 JOI 国没有电缆。

I 先生有一个 $C$ 天的电缆建设计划。第 $(i+1)\ (0\le i\le C-1)$​ 天的计划用三个整数 $T_i,X_i,Y_i$ 表示，分别表示：

• 如果 $T_i=0$，他们会架设一段连接城镇 $X_i$ 与城镇 $Y_i$ 的电缆。保证在第 $(i+1)$ 天开始的时候城镇 $X_i$ 与城镇 $Y_i$ 之间没有电缆。
• 如果 $T_i=1$​，他们会拆除一段连接城镇 $X_i$​ 与城镇 $Y_i$​ 的电缆。保证在第 $(i+1)$​ 天开始的时候城镇 $X_i$​ 与城镇 $Y_i$​ 之间有电缆。

JOI 国经常发生山体滑坡。如果在城镇 $x$ 与 $x+1\ (0\le x\le N-2)$​ 之间发生山体滑坡，则连接编号至多为 $x$ 与编号至少为 $x+1$​ 城镇的电缆就不可用了。在 JOI 国，每当山体滑坡发生，他们就会选择一些城镇建设基站。基站应满足对于任意城镇，都可以通过一些可用的电缆与基站连通。

I 先生在建设阶段就在考虑山体滑坡发生时应建设多少基站。他有 $Q$ 个问题：第 $(j+1)$ 个问题用两个整数 $W_j,P_j$ 表示，表示他想知道在 $(W_j+1)$ 天结束时，如果在城镇 $P_j$ 和 $P_j+1$ 之间发生山体滑坡，至少应该建立多少基站。

你作为 I 先生的助理，负责写一个程序去回答 I 先生的问题。

样例

考虑有 $5$ 个城镇的情况。接下来用 $(x,y)$ 代表连接城镇 $x$ 和城镇 $y$ 的电缆。

• 假设当有四根电缆 $(0,1),(1,3),(2,4),(4,0)$ 时，在城镇 $1$ 和 $2$ 之间发生了滑坡。电缆 $(1,3)$ 和 $(4,0)$ 不可用了，因此可用的电缆是 $(0,1)$ 和 $(2,4)$。你需要在城镇 $0,2,3$ 建立基站。最少要建立基站数为 $3$。
• 假设当有六根电缆 $(0, 1), (0, 3), (1, 2), (2, 4), (4, 0)$​​ 和 $(4,3)$​​ 时，在城镇 $3$​​ 和 $4$​​ 之间发生了滑坡。电缆 $(2,4),(4,0)$​​ 和 $(4,3)$​​ 不可用了，因此可用的电缆是 $(0,1),(0,3)$​​ 和 $(1,2)$​​。你需要在城镇 $0$​​ 和 $4$ 建立基站。最少要建立基站数为 $2$​​。

子任务

本题有四个子任务。子任务分值及附加限制如下表所示：

实现细节

你需要实现如下函数 $\texttt{simulateCollapse}$ 以回答 $Q$ 个问题。

• $\texttt{simulateCollapse(N, T, X, Y, W, P)}$
  • $\texttt N$：JOI 国的城镇个数。
  • $\texttt{T, X, Y}$：长度为 $C$ 的数组。对于 $0\le i\le C-1$，$T_i,X_i,Y_i$ 表示在第 $(i+1)$ 天的建设计划。保证 $T_i$ 等于 $0$ 或 $1$，并且保证 $0\le X_i\le N-1,0\le Y_i\le N-1,X_i\neq Y_i$。
  • $\texttt{W, P}$：长度为 $Q$ 的数组。对于 $0\le i\le Q-1$，$W_j,P_j$ 表示第 $(j+1)$ 个询问，保证 $0\le W_j\le C-1,0\le P_j\le N-2$。
  • 这个函数应当返回一个长度为 $Q$ 的数组 $D$。对于 $0\le j\le Q-1$，$D_j$ 应该是对第 $(j+1)$​ 个问题的回答。

C++ 的提交应引入库 $\texttt{collapse.h}$​ 来完成，目前不支持对 Java 和 Pascal 语言提交的测评。

样例交互器

样例交互器按如下格式读取输入：

第一行三个整数 $N,C,Q$。

接下来 $C$ 行，每行三个整数 $T_i,X_i,Y_i$。

接下来 $Q$ 行，每行两个整数 $W_j,P_j$。

样例交互器按如下方式输出 $\texttt{simulateCollapse}$​ 函数的返回值：

第 $j+1$ 行输出 $D_j$。