この問題は

• それぞれの鳩がどの巣にいるか
• それぞれの巣に鳩が何匹いるか
• 鳩が複数いる巣が何個あるか

を管理することで解くことができます．鳩 \(i\) がいる巣を \(\mathrm{pos}[i]\)，巣 \(i\) にいる鳩の数を \(\mathrm{cnt}[i]\)，鳩が複数いる巣の数を \(\mathrm{ans}\) とします．クエリ \(2\) では \(\mathrm{ans}\) を出力すればよいです．

クエリ \(1\) について考えます．鳩 \(P\) の移動によって \(\mathrm{ans}\) が変わるのは以下の \(2\) つが考えられます．

• もともと鳩 \(P\) がいた巣にいる鳩の数が \(2\) から \(1\) に減ったとき
• 鳩 \(P\) が巣 \(H\) に移動したあとに，巣 \(H\) にいる鳩の数が \(1\) から \(2\) に増えたとき

これを踏まえたうえで，鳩 \(P\) の移動に応じて \(\mathrm{pos}, \mathrm{cnt}, \mathrm{ans}\) を変更すればよいです．詳しくは実装例をご覧ください．

N, Q = map(int, input().split())
ans = 0
cnt = [0] + [1] * N
pos = list(range(N + 1))
for i in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        P, H = query[1:]
        # 鳩 P は移動する前は巣 pos[P] にいる
        # 鳩 P が移動することで 巣 pos[P] にいる鳩の数が 2 から 1 に減る場合, ans を 1 減らす
        if cnt[pos[P]] == 2:
            ans -= 1
        # 巣 pos[P] の鳩の数を 1 減らす
        cnt[pos[P]] -= 1

        # 鳩 P がいる巣を H に変更する
        pos[P] = H
        # 巣 H の鳩の数を 1 増やす
        cnt[pos[P]] += 1
        # 鳩 P が移動することで 巣 H にいる鳩の数が 1 から 2 に増える場合，ans を 1 増やす
        if cnt[pos[P]] == 2:
            ans += 1
    else:
        print(ans)