← 返回题目列表

Codeforces · 1548/A

A. 谎言之网

中文机器翻译题面 查看原题

有$$$n$$$贵族,编号从$$$1$$$到$$$n$$$。高贵$$$i$$$拥有$$$i$$$的力量。还有$$$m$$$“友谊”。贵族$$$a$$$和$$$b$$$之间的友谊总是相互的。

如果满足以下两个条件,则贵族被定义为易受攻击:

- 贵族至少有一个朋友,并且
- 该贵族的所有朋友都拥有更高的力量。

您将必须处理以下三种类型的查询。

1.添加贵族$$$u$$$和$$$v$$$之间的友谊。
2. 删除贵族$$$u$$$和$$$v$$$之间的友谊。
3. 计算以下过程的答案。

流程:所有弱势贵族同时被杀,所有友谊结束。那么,新的贵族就有可能变得脆弱。这个过程不断重复,直到没有贵族受到攻击。可以证明该过程将在有限时间内结束。该过程完成后,您需要计算剩余的贵族数量。

请注意,该过程的结果不会在查询之间延续,也就是说,每个过程都以所有贵族都活着开始!

输入

第一行包含整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 2\cdot 10^5$$$, $$$0 \le m \le 2\cdot 10^5$$$) — 分别是贵族数量和原始友谊数量。

接下来的 $$$m$$$ 行每行包含整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$),描述友谊。没有友谊会被列出两次。

下一行包含整数 $$$q$$$ ($$$1 \le q \le 2\cdot {10}^{5}$$$) — 查询数。

接下来的 $$$q$$$ 行包含查询本身,每个查询具有以下三种格式之一。

- $$$1$$$ $$$u$$$ $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$) — 在 $$$u$$$ 和 $$$v$$$ 之间添加好友关系。可以保证$$$u$$$ 和$$$v$$$ 此时不是朋友。
- $$$2$$$ $$$u$$$ $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$) — 删除 $$$u$$$ 和 $$$v$$$ 之间的好友关系。可以保证$$$u$$$和$$$v$$$此时是朋友。
- $$$3$$$ — 打印语句中描述的过程的答案。

输出

对于每种类型 $$$3$$$ 查询,将一个整数打印到新行。保证至少有一种类型$$$3$$$查询。

示例

输入 #1

4 3
2 1
1 3
3 4
4
3
1 2 3
2 3 1
3

输出 #1

2
1

输入 #2

4 3
2 3
3 4
4 1
1
3

输出 #2

1

注意

考虑第一个例子。在第一个类型 3 查询中,我们有下图。

在第一轮过程中,贵族$$$1$$$比他所有的朋友($$$2$$$和$$$3$$$)都弱,因此被杀死。在第 1 轮中,没有其他贵族是脆弱的。在第 2 轮中,贵族 $$$3$$$ 比他唯一的朋友贵族 $$$4$$$ 弱,因此被杀死。至此,流程结束,答案为$$$2$$$。

在第二个类型 3 查询中,唯一幸存的贵族是 $$$4$$$。

第二个示例仅包含一种类型 $$$3$$$ 查询。第一轮,杀死两名贵族,第二轮,杀死一名贵族。最终答案是 $$$1$$$,因为只有一名贵族幸存。