問題文

1,2,3,...,N1,2,3,...,N と番号が振られた NN 個の国があります。
QQ 個のクエリが与えられるので,順番に処理してください。各クエリは以下の 33 種類のいずれかです。
1 x y :現時点の国の番号の最大値を MM とする。国 xx と国 yy が統合して無くなり,新たに国 M+1M+1 が建国される。
2 x :現時点の国の番号の最大値を MM とする。国 xx が分断して無くなり,新たに国 M+1,M+2M+1,M+2 が建国される。
3 :現時点の国の数を出力する。

制約

  • 1N10181 \leq N \leq 10^{18}
  • 1Q1051 \leq Q \leq 10^{5}
  • 各クエリは 33 種類のいずれか
  • クエリ 11 では,1xM1 \leq x \leq M, 1yM1 \leq y \leq M, xy x \neq y
  • クエリ 11 では,その時点で x,yx,y は存在する
  • クエリ 22 では,1xM1 \leq x \leq M
  • クエリ 22 では,その時点で xx は存在する
  • クエリ 3311 つ以上存在する
  • 入力はすべて整数

入力

NNQQ
query1query_1
query2query_2
query3query_3
...
queryQquery_Q

ただし,queryiquery_iii 番目のクエリを表しており,次の形式のいずれかで与えられる。

1 x y
2 x
3

出力

クエリ 33 の回数を qq とすると,qq 行出力してください。
i=1,2,3,...,qi = 1,2,3,...,q として,ii 行目には ii 個目のクエリ 33 に対する答えを出力してください。

サンプル1

入力
5 5
1 2 3
3
2 4
2 6
3
出力
4
6

はじめは,国 1,2,3,4,51,2,3,4,5 が存在します。
11 個目のクエリで,国 22 と国 33 が統合して無くなり国 66 が建国されるので,結果として国 1,4,5,61,4,5,6 が存在します。
22 個目のクエリで,現時点の国の数 44 を出力します。
33 個目のクエリで,国 44 が分断して無くなり国 7,87,8 が建国されるので,結果として国 1,5,6,7,81,5,6,7,8 が存在します。
44 個目のクエリで,国 66 が分断して無くなり国 9,109,10 が建国されるので,結果として国 1,5,7,8,9,101,5,7,8,9,10 が存在します。
55 個目のクエリで,現時点の国の数 66 を出力します。

サンプル2

入力
3 3
1 1 2
1 3 4
3
出力
1

サンプル3

入力
1000 1
3
出力
1000

サンプル4

入力
100 10
2 67
2 33
1 49 12
2 96
3
1 10 101
1 2 3
1 102 103
3
3
出力
102
99
99

Submit


Go (1.21)