CF1548A.Web of Lies

When you play the game of thrones, you win, or you die. There is no middle ground.

Cersei Lannister, A Game of Thrones by George R. R. Martin

There are $n$ nobles, numbered from $1$ to $n$. Noble $i$ has a power of $i$. There are also $m$ "friendships". A friendship between nobles $a$ and $b$ is always mutual.

A noble is defined to be vulnerable if both of the following conditions are satisfied:

• the noble has at least one friend, and
• all of that noble's friends have a higher power.

You will have to process the following three types of queries.

1. Add a friendship between nobles $u$ and $v$.
2. Remove a friendship between nobles $u$ and $v$.
3. Calculate the answer to the following process.

The process: all vulnerable nobles are simultaneously killed, and all their friendships end. Then, it is possible that new nobles become vulnerable. The process repeats itself until no nobles are vulnerable. It can be proven that the process will end in finite time. After the process is complete, you need to calculate the number of remaining nobles.

Note that the results of the process are not carried over between queries, that is, every process starts with all nobles being alive!

当你玩权力的游戏时，你或者赢，或者死。没有中间地带。

——瑟曦·兰尼斯特，《权力的游戏》，乔治·R·R·马丁 著

共有 $n$ 位贵族，编号从 $1$ 到 $n$。贵族 $i$ 的权势为 $i$。此外还有 $m$ 对“友谊”关系。贵族 $a$ 与 $b$ 之间的友谊总是双向的（即无向）。

若一位贵族满足以下两个条件，则称其为易受攻击的（vulnerable）：

• 该贵族至少拥有一位朋友；且
• 该贵族的所有朋友的权势均严格高于他/她。

你需要处理以下三类查询：

1. 在贵族 $u$ 与 $v$ 之间添加一条友谊关系；
2. 在贵族 $u$ 与 $v$ 之间移除一条友谊关系；
3. 计算如下过程的最终结果：

该过程定义如下：
所有易受攻击的贵族同时被杀死，且他们所有的友谊关系均立即终止。随后，可能有新的贵族因此变为易受攻击的。该过程不断重复，直至不再存在任何易受攻击的贵族为止。可以证明，该过程必将在有限步内终止。当过程结束后，你需要计算剩余贵族的数量。

注意：每次第 3 类查询所执行的过程彼此独立，即每次过程均从所有 $n$ 位贵族均存活的状态开始！

The first line contains the integers $n$ and $m$ ($1 \le n \le 2\cdot 10^5$, $0 \le m \le 2\cdot 10^5$) — the number of nobles and number of original friendships respectively.

The next $m$ lines each contain the integers $u$ and $v$ ($1 \le u,v \le n$, $u \ne v$), describing a friendship. No friendship is listed twice.

The next line contains the integer $q$ ($1 \le q \le 2\cdot {10}^{5}$) — the number of queries.

The next $q$ lines contain the queries themselves, each query has one of the following three formats.

• $1$ $u$ $v$ ($1 \le u,v \le n$, $u \ne v$) — add a friendship between $u$ and $v$. It is guaranteed that $u$ and $v$ are not friends at this moment.
• $2$ $u$ $v$ ($1 \le u,v \le n$, $u \ne v$) — remove a friendship between $u$ and $v$. It is guaranteed that $u$ and $v$ are friends at this moment.
• $3$ — print the answer to the process described in the statement.

第一行包含两个整数 $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$ —— 输出题目陈述中所描述过程的答案。

For each type $3$ query print one integer to a new line. It is guaranteed that there will be at least one type $3$ query.

对于每个类型 $3$ 的查询，在新的一行输出一个整数。保证至少存在一个类型 $3$ 的查询。

Consider the first example. In the first type 3 query, we have the diagram below.

In the first round of the process, noble $1$ is weaker than all of his friends ($2$ and $3$), and is thus killed. No other noble is vulnerable in round 1. In round 2, noble $3$ is weaker than his only friend, noble $4$, and is therefore killed. At this point, the process ends, and the answer is $2$.

In the second type 3 query, the only surviving noble is $4$.

The second example consists of only one type $3$ query. In the first round, two nobles are killed, and in the second round, one noble is killed. The final answer is $1$, since only one noble survives.

考虑第一个例子。在第一个类型 3 的查询中，我们有下方的示意图。

在该过程的第一轮中，贵族 $1$ 比他所有的朋友（即贵族 $2$ 和 $3$）都更弱，因此被杀死。第一轮中没有其他贵族处于易受攻击状态。在第二轮中，贵族 $3$ 比他唯一的朋友——贵族 $4$ 更弱，因此被杀死。此时过程结束，答案为 $2$。

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

第二个例子仅包含一个类型 $3$ 的查询。在第一轮中，两名贵族被杀死；在第二轮中，一名贵族被杀死。最终答案为 $1$，因为仅剩一名贵族幸存。