题目描述

最初 $N$ 頂点 $0$ 辺の無向グラフがあり、各頂点には $1$ から $N$ まで番号がついています。
$Q$ 個のクエリが与えられるので、順に処理し、各クエリの後における「他のどの頂点とも辺で結ばれていない頂点」の数を出力してください。

$i$ 個目のクエリは $\mathrm{query}_i$ であり、各クエリは次の $2$ 種類いずれかです。

• 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$ 個目のクエリを処理した後の「他のどの頂点とも辺で結ばれていない頂点」の数を出力せよ。

题目大意

给定一个有 $n$ 个点的无向图。初始没有任何边。

接下来有 $q$ 次操作，分为 $2$ 种类型：

• 1 u v：连接 $u$ 和 $v$,保证没有重边、自环。

• 2 v：删除连接 $v$ 的所有边。

每次操作后，输出没有连接其它任何点的点的数量（即度数为 $0$ 的点的数量）。

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$ 番目の種類のクエリにおいて、$1\leq\ u,v\leq\ N$, $u\neq\ v$
• $2$ 番目の種類のクエリにおいて、$1\leq\ v\leq\ N$
• $1$ 番目の種類のクエリの直前の時点で、そのクエリの $u,v$ について頂点 $u$ と頂点 $v$ は辺で結ばれていない。
• 入力はすべて整数

Sample Explanation 1

$1$ 個目のクエリの後で、頂点 $1$ と頂点 $2$ は互いに結ばれており、頂点 $3$ のみが他のどの頂点とも辺で結ばれていません。 よって、$1$ 行目には $1$ を出力します。 また、$3$ 個目のクエリの後でどの相異なる $2$ 頂点の間も辺で結ばれていますが、$4$ 個目のクエリによって、 頂点 $1$ と他の頂点を結ぶ辺、すなわち 頂点 $1$ と頂点 $2$ を結ぶ辺および頂点 $1$ と頂点 $3$ を結ぶ辺が削除されます。 この結果として、頂点 $2$ と頂点 $3$ は互いに結ばれているが、頂点 $1$ は他のどの頂点とも辺で結ばれていない状態となります。 よって、$3$ 行目には $0$ を、$4$ 行目には $1$ を出力します。

Sample Explanation 2

$2$ 番目の種類のクエリを行う直前の時点で、すでにその頂点と他の頂点を結ぶ辺が $1$ 本も存在しないこともあります。