Logo Universal Online Judge

UOJ

时间限制:3 s 空间限制:512 MB

#2732. 随机(random)

统计

题目描述

你需要维护一个动态的有 n 个点的无向图 ,支持连边与删边,图的节点的标号为 1-n。一共会有 m 次操作。一开始图中没有任何边。

同时你也需要接受 Q 个问询事件,其中第 i 个问询事件为:对于在第 ti 次操作后的图,如果所有满足 一个端点 <= pi,另一个端点 > pi 的边突然消失,请你需要输出此时图的连通块数量。

输出格式

第一行三个正整数 n,m,Q 。 之后 行每行三个非负整数 op, x, y。若 op = 0,则表示加入边 (x, y);若 op = 1,则表示删除边 (x,y)。保证删除的边一定存在,且任意时刻图无重边无自环。 之后 Q 行每行两个正整数,表示 ti,pi。

输出格式

Q 行,每行一个整数表示一次询问的答案。

样例输入1

3 2 2
0 1 3
0 2 3
2 2
2 1

样例输出1

3
2

样例输入2

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


## 样例输出2

3 2 ```

数据范围

对于所有数据,1 <= n, m, Q <= 10^5

Subtask1(24pts): n, m, Q <= 5000

Subtask2(25pts): 所有询问中的 pi 均相等。

Subtask3(25pts): 只有加边操作。

Subtask4(26pts): 无特殊限制。