Problem:


Problem D: Graph Construction

n 匹のうさぎがいて, 0 番からn − 1 番の番号がついた小屋に1 匹ずつ住んでいる.

あるとき, 秘密の組織によって地下通路の建設工事が行われる, という情報がうさぎたちのもとへ入った. 地下通路を使えば, うさぎたちは他のうさぎたちの小屋へ遊びに行けるようになって嬉しい.

通路は両方向に進むことができ, また通路同士は交わらない. 諸事情により, 一度建設された通路が破壊されてしまうこともある. 通路の建設や破壊の工事は1 本ずつ行われ, 各工事中はうさぎは自分の小屋に留まっているものとする.

うさぎたちは, 工事のいくつかの段階において, あるうさぎとあるうさぎが遊べるかどうかを事前に知りたい. うさぎたちは仲良しなので, 遊びに行くときに他のうさぎの小屋を自由に通ることができる. プログラミングが好きなうさぎたちは, 昔似たような問題を解いたので簡単だろうと思って挑戦し出したが, なかなか効率の良いプログラムが書けない. うさぎの代わりにこの問題を解け.

Input

入力の一行目にはn とk がスペース区切りで与えられる。2 ≤ n ≤ 40 000, 1 ≤ k ≤ 40 000

つづくk 行には工事情報と質問が合わせて, 時間順に与えられる.

 “1 u v” — 小屋u とv を結ぶ通路が建設される. 小屋u とv を結ぶ通路がないときにのみ現れる.

 “2 u v” — 小屋u とv を結ぶ通路が破壊される. 小屋u とv を結ぶ通路があるときにのみ現れる.

 “3 u v” — 小屋u とv のうさぎが遊べるかどうか判定せよ.

0 ≤ u < v < n

Output

入力に現れる各質問について, 遊べるなら”YES”を, そうでないなら”NO”を1 行ずつ出力せよ.

Sample Input 1

4 10
1 0 1
1 0 2
3 1 2
2 0 1
1 2 3
3 0 1
1 0 1
2 0 2
1 1 3
3 0 2

Sample Output 1

YES
NO
YES



Sample input:
4 10
1 0 1
1 0 2
3 1 2
2 0 1
1 2 3
3 0 1
1 0 1
2 0 2
1 1 3
3 0 2


Sample output:
YES
NO
YES

Submission status: Accepted

Solution code:
from collections import deque
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    N, K = map(int, readline().split())
    ES = [list(map(int, readline().split())) for i in range(K)]
    emp = {}
    sq = int(K**.5) + 1
    def root(x):
        if x == p[x]:
            return x
        p[x] = y = root(p[x])
        return y
    def unite(x, y):
        px = root(x); py = root(y)
        if px < py:
            p[py] = px
        else:
            p[px] = py
    que = deque()
    used = [0]*N
    lb = 0

    p = [0]*N
    for i in range(sq):
        s = set()
        for j in range(i*sq, min(i*sq+sq, K)):
            t, a, b = ES[j]
            if t == 3:
                continue
            e = (a, b)
            if emp.get(e, 0):
                s.add(e)
            emp[e] = 0

        p[:] = range(N)
        for (v, w), d in emp.items():
            if d == 1:
                unite(v, w)

        G0 = [[] for i in range(N)]
        emp0 = {}
        for a, b in s:
            pa = root(a); pb = root(b)
            if pa == pb:
                continue
            e = (pa, pb) if pa < pb else (pb, pa)
            if e in emp0:
                e1, e2 = emp0[e]
                e1[1] = e2[1] = e1[1] + 1
            else:
                e1 = [pb, 1]; e2 = [pa, 1]
                G0[pa].append(e1)
                G0[pb].append(e2)
                emp0[e] = e1, e2

        for j in range(i*sq, min(i*sq+sq, K)):
            t, a, b = ES[j]
            pa = root(a); pb = root(b)
            e = (pa, pb) if pa < pb else (pb, pa)
            if t == 1:
                emp[a, b] = 1
                if pa == pb:
                    continue
                if e not in emp0:
                    e1 = [pb, 1]; e2 = [pa, 1]
                    G0[pa].append(e1)
                    G0[pb].append(e2)
                    emp0[e] = e1, e2
                else:
                    e1, e2 = emp0[e]
                    e1[1] = e2[1] = e1[1] + 1
            elif t == 2:
                emp[a, b] = 0
                if pa == pb:
                    continue
                e1, e2 = emp0[e]
                e1[1] = e2[1] = e1[1] - 1
            elif t == 3:
                if pa == pb:
                    write("YES\n")
                else:
                    lb += 1
                    que.append(pa)
                    used[pa] = lb
                    while que:
                        v = que.popleft()
                        for w, d in G0[v]:
                            if d and used[w] != lb:
                                used[w] = lb
                                que.append(w)
                    if used[pb] == lb:
                        write("YES\n")
                    else:
                        write("NO\n")
solve()