Isolation

题目描述

有一个无向图，包含编号为 $1$ 到 $N$ 的 $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)$ 应包含不与任何其他顶点通过边相连的顶点数。

3 7
1 1 2
1 1 3
1 2 3
2 1
1 1 2
2 2
1 1 2

1
0
0
1
0
3
1

2 1
2 1

2

提示

$2 \leq N\leq 3\times 10^5$ $1 \leq Q\leq 3\times 10^5$ 对于每个第一类查询，$1\leq u,v\leq N$ 且 $u\neq v$。 对于每个第二类查询，$1\leq v\leq N$。 在给出第一类查询之前，顶点 $u$ 和顶点 $v$ 之间不存在边。 输入中的所有数值均为整数。在第一个查询之后，顶点 $1$ 和顶点 $2$ 彼此通过一条边相连，但顶点 $3$ 不与任何其他顶点相连。
因此，第一行应输出 $1$。 在第三个查询之后，所有不同顶点的对都被边连接。
然而，第四个查询要求删除连接顶点 $1$ 与其他顶点的所有边，具体地删除顶点 $1$ 与顶点 $2$ 之间的边，以及顶点 $1$ 与顶点 $3$ 之间的边。 因此，顶点 $2$ 和顶点 $3$ 彼此相连，而顶点 $1$ 不与任何其他顶点通过边相连。
因此，第三行和第四行分别应输出 $0$ 和 $1$。
当给出第二类查询时，可能不存在连接该顶点与其他顶点的边。

标签: AtCoder|abc302E

来源

AtCoder|abc302E