JOI 国的深长山谷中有 $N$ 座城镇。城镇按距离海边的远近依次编号为 $0, 1, \dots, N-1$。

JOI 国科学委员会主席 I 先生计划在城镇之间维护双向通信电缆。目前 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$ 的电缆。

• 假设当前有 4 条电缆 $(0, 1), (1, 3), (2, 4)$ 和 $(4, 0)$，在城镇 1 和城镇 2 之间发生滑坡。电缆 $(1, 3)$ 和 $(4, 0)$ 失效，因此可用的电缆为 $(0, 1)$ 和 $(2, 4)$。你可以在城镇 0、2 和 3 安装基站。所需的最少基站数量为 3。
• 假设当前有 6 条电缆 $(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。

子任务

共有 4 个子任务。各子任务的分数和约束如下：

实现细节

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

• simulateCollapse(N, T, X, Y, W, 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 j \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)$ 个询问的答案。

样例评测程序

样例评测程序按以下格式读取输入： 第 1 行：$N \ C \ Q$ 第 $2+i$ 行（$0 \le i \le C-1$）：$T_i \ X_i \ Y_i$ * 第 $2+C+j$ 行（$0 \le j \le Q-1$）：$W_j \ P_j$

样例评测程序按以下格式打印 simulateCollapse 的返回值： * 第 $1+j$ 行（$0 \le j \le Q-1$）：$D_j$