株式会社n0ma_ru

2 secs 1024 MB
n0ma_ru's icon n0ma_ru

問題文

株式会社n0ma_ruにはNN人の社員が居て、それぞれ社員11、社員22\cdots、社員NNと呼ぶことにします。 このNN人でじゃんけんにより上下関係を決定します。社員XXと社員YYがじゃんけんをして、社員XXが勝利したら社員YYは社員XXの部下になります。また、既に社員YYに部下がいたら、社員YYの全ての部下が社員XXの部下になります。逆に、社員XXは社員YYの上司になると言う事とします。

QQ個のクエリが与えられるので、順に処理してください。ii個目のクエリはquery i{}_iであり、各クエリは次の33種類のいずれかです。

  • 1 x y:社員xxと社員yyがじゃんけんし、社員xxが勝利します。このクエリが与えられる直前の時点で、社員xxと社員yyはどちらも上司を一人も持たないものとします。
  • 2 x:その時点で、社員xxの部下の数を求めて、出力してください。
  • 3:その時点で、上司を一人も持たない社員の人数を求めて出力してください。

制約

  • 2N3×1052 \le N \le 3 \times 10^5
  • 1Q3×1051 \le Q \le 3 \times 10^5
  • 1番目の形式のクエリにおいて、1x,yN1 \le x,y \le N
  • 2番目の形式のクエリにおいて、1xN1 \le x \le N
  • 入力はすべて整数です。
  • 2番目の形式または3番目の形式のクエリは1回以上登場します。

入力

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

N Qquery1query2queryQN\ Q\\query_1\\query_2\\\vdots\\query_Q

出力

query i{}_i22番目の形式か33番目の形式であるようなi(1iQ)i(1 \le i \le Q)の個数をXXとして、XX行出力せよ。j(1jX)j(1 \le j \le X)行目にはそのようなクエリの内jj番目のクエリに対する答えを出力してください。最後に改行してください。

入力例1

3 6
3
2 1
1 2 3
1 1 2
2 2
3

出力例1

3
0
1
1

社員は33人です。以下のようにクエリが行われます。

  • この時点で上司を一人も持たない社員の人数は33人のため33を出力します。
  • この時点での社員11の部下の人数は00人のため00を出力します。
  • 社員22と社員33がじゃんけんをして社員22が勝利しました。これにより社員33が社員22の部下になりました。
  • 社員11と社員22がじゃんけんをして社員11が勝利しました。これにより社員22、社員3322人が社員11の部下になりました。
  • この時点での社員22の部下は社員33のみのため、11を出力します。
  • この時点で上司を一人も持たない社員は社員11のみのため、11を出力します。

入力例2

3 2
2 1
3

出力例2

0
3

じゃんけんが一度も行われない場合もあります。

提出


Go (1.21)