当前没有测试数据。

E - 孤立点

分数 : $425$ 分

问题描述

有一个无向图，有 $N$ 个顶点编号从 $1$ 到 $N$，初始时边数为 $0$。
给定 $Q$ 个查询，按顺序处理它们。在处理每个查询后， 打印出不被任何边连接到其他顶点的顶点的数量。

第 $i$ 个查询 $\mathrm{query}_i$，是以下两种情况之一。

• 1 u v：连接顶点 $u$ 和顶点 $v$ 成为一条边。保证在给定这个查询时，顶点 $u$ 和顶点 $v$ 之间不存在边。

• 2 v：移除连接顶点 $v$ 与其他顶点的所有边。（顶点 $v$ 本身不会被移除。）

约束

• $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$ 之间没有边。
• 输入中的所有值都为整数。

输入

从标准输入中按以下格式给出：

$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

第一个查询后，顶点 $1$ 和顶点 $2$ 之间被一条边连接，但是顶点 $3$ 没有与其他任何顶点相连。
因此，在第一行应该输出 $1$。

第三个查询后，所有不同的顶点对都被一条边相连。
然而，第四个查询要求移除连接顶点 $1$ 与其他顶点的所有边，具体说就是移除顶点 $1$ 和顶点 $2$ 之间的边，以及顶点 $1$ 和顶点 $3$ 之间的边。 结果是，顶点 $2$ 和顶点 $3$ 之间被一条边连接，而顶点 $1$ 没有与其他任何顶点相连。
因此，在第三行和第四行分别应该输出 $0$ 和 $1$。

2 1
2 1

2

当给出第二种查询时，可能没有边连接该顶点和其他顶点。