有$$$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$$$,因为只有一名贵族幸存。