题目描述

译自 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 先生的问题。

实现细节

函数定义

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

std::vector<int> simulateCollapse(
    int N, 
    std::vector<int> T, 
    std::vector<int> X, 
    std::vector<int> Y, 
    std::vector<int> W, 
    std::vector<int> P
)

参数说明

• N：JOI 国的城镇个数。

• 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$。

• 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++ 的提交应引入库 collapse.h 来完成，目前不支持对 Java 和 Pascal 语言提交的测评。

输入格式

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

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

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

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

输出格式

样例交互器按如下方式输出 simulateCollapse 函数的返回值：

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

5 8 2
0 0 1
0 1 3
0 2 4
0 4 0
1 1 3
0 0 3
0 1 2
0 4 3
3 1
7 3

3
2

样例

考虑有 $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$。

数据规模与约定

$2 < N \leq 100000$

$1 < C \leq 100000$

$1 < Q \leq 100000$