配点 : $425$ 点

問題文

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

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

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

入力

入力は以下の形式で標準入力から与えられる。

$N$ $Q$

$\mathrm{query}_1$

$\mathrm{query}_2$

$\vdots$

$\mathrm{query}_Q$

出力

$Q$ 行出力せよ。 $i$ 行目 $(1\leq i\leq Q)$ には、$i$ 個目のクエリを処理した後の「他のどの頂点とも辺で結ばれていない頂点」の数を出力せよ。

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$ 個目のクエリの後で、頂点 $1$ と頂点 $2$ は互いに結ばれており、頂点 $3$ のみが他のどの頂点とも辺で結ばれていません。 よって、$1$ 行目には $1$ を出力します。

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

2 1
2 1

2

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