孤立

题目描述

有一个顶点编号为 $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 \le i \le 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

第一个查询后，顶点 $1$ 和顶点 $2$ 通过边相连，但顶点 $3$ 没有与其他任何顶点相连。

因此第 $1$ 行应输出 $1$。

第三个查询后，所有不同的顶点对之间都有边相连。

但是，第四个查询要求删除连接顶点 $1$ 与其他顶点的所有边，具体来说就是删除顶点 $1$ 和顶点 $2$ 之间的边，以及顶点 $1$ 和顶点 $3$ 之间的边。 结果是顶点 $2$ 和顶点 $3$ 相连，而顶点 $1$ 没有通过任何边与其他顶点相连。

因此第 $3$ 行和第 $4$ 行应分别输出 $0$ 和 $1$。

2 1
2 1

2

发出第二种查询时，该顶点可能没有与其他顶点相连的边。

数据范围

• $2 \le N \le 3 \times 10^5$
• $1 \le Q \le 3 \times 10^5$
• 对于第一种查询，$1 \le u,v \le N$ 且 $u \neq v$。
• 对于第二种查询，$1 \le v \le N$。
• 在第一种查询发出之前，顶点 $u$ 和顶点 $v$ 之间没有边。
• 输入中的所有值均为整数。