AT_abc302_e [ABC302E] Isolation

最初有一个包含 $N$ 个顶点、$0$ 条边的无向图，每个顶点编号为 $1$ 到 $N$。 现在给出 $Q$ 个操作，请依次处理每个操作，并在每次操作后输出“没有与任何其他顶点通过边相连的顶点”的数量。 第 $i$ 个操作记作 $\mathrm{query}_i$，每个操作有以下两种类型之一： - `1 u v`：在顶点 $u$ 和顶点 $v$ 之间添加一条边。保证在该操作之前，$u$ 和 $v$ 之间没有边。 - `2 v`：删除顶点 $v$ 与所有其他顶点之间的边（顶点 $v$ 本身不会被删除）。

输入从标准输入读入，格式如下： > $N$ $Q$ > $\mathrm{query}_1$ > $\mathrm{query}_2$ > $\vdots$ > $\mathrm{query}_Q$

输出共 $Q$ 行。 第 $i$ 行（$1\leq i\leq Q$）输出处理完第 $i$ 个操作后，“没有与任何其他顶点通过边相连的顶点”的数量。

### 限制条件 - $2\leq N\leq 3\times 10^5$ - $1\leq Q\leq 3\times 10^5$ - 对于类型 $1$ 的操作，$1\leq u,v\leq N$ 且 $u\neq v$ - 对于类型 $2$ 的操作，$1\leq v\leq N$ - 对于类型 $1$ 的操作，保证操作前 $u$ 和 $v$ 之间没有边 - 所有输入均为整数 ### 样例解释 1 在第 $1$ 个操作后，顶点 $1$ 和顶点 $2$ 之间有一条边，只有顶点 $3$ 没有与任何其他顶点通过边相连。因此，第 $1$ 行输出 $1$。 在第 $3$ 个操作后，所有不同的两个顶点之间都有边相连，但第 $4$ 个操作会删除顶点 $1$ 与其他顶点之间的所有边，即删除顶点 $1$ 与顶点 $2$ 之间的边，以及顶点 $1$ 与顶点 $3$ 之间的边。 这样，顶点 $2$ 和顶点 $3$ 之间仍有边，但顶点 $1$ 不再与任何其他顶点相连。因此，第 $3$ 行输出 $0$，第 $4$ 行输出 $1$。 ### 样例解释 2 在进行类型 $2$ 的操作之前，可能已经不存在任何与该顶点相连的边。 由 ChatGPT 4.1 翻译