Forced Online Queries Problem
You are given an undirected graph with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. Initially there are no edges.You are asked to perform some queries on the graph. Let $$$last$$$ be the answer to the latest query of the second type, it is set to $$$0$$$ before the first such query. Then the queries are the following:  $$$1~x~y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$) — add an undirected edge between the vertices $$$(x + last - 1)~mod~n + 1$$$ and $$$(y + last - 1)~mod~n + 1$$$ if it doesn't exist yet, otherwise remove it;  $$$2~x~y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$) — check if there exists a path between the vertices $$$(x + last - 1)~mod~n + 1$$$ and $$$(y + last - 1)~mod~n + 1$$$, which goes only through currently existing edges, and set $$$last$$$ to $$$1$$$ if so and $$$0$$$ otherwise. Good luck!
The converted queries in the first example are:  1 1 2  1 1 3  2 3 2  1 3 5  2 4 5  1 2 4  2 3 4  1 2 4  2 5 4 The converted queries in the second example are:  1 1 2  1 2 3  1 3 1  2 1 3  1 1 3  2 3 1  1 2 3  2 2 3  2 1 2 
The first line contains two integer numbers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 2 \cdot 10^5$$$) — the number of vertices and the number of queries, respectively.Each of the following $$$m$$$ lines contains a query of one of two aforementioned types. It is guaranteed that there is at least one query of the second type.
Print a string, consisting of characters '0' and '1'. The $$$i$$$-th character should be the answer to the $$$i$$$-th query of the second type. Therefore the length of the string should be equal to the number of queries of the second type.
from collections import defaultdict
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (rs, rt) = (get_root(s), get_root(t))
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        rank[rs] += 1
    if rank[s] >= rank[t]:
        root[rt] = rs
    else:
        root[rs] = rt
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False

def bfs(s, g, c):
    (q, k) = ([s], 0)
    color[s] = c
    while len(q) ^ k:
        i = q[k]
        for j in G[i]:
            if j == g:
                return True
            if color[j] ^ c:
                q.append(j)
                color[j] = c
        k += 1
    return False
(n, m) = map(int, input().split())
txy = [tuple(map(int, input().split())) for _ in range(m)]
l = 12345
e = set()
G = [set() for _ in range(n + 1)]
color = [-1] * (n + 1)
last = 0
ans = []
for i in range(m // l + min(m % l, 1)):
    e1 = set()
    for j in range(i * l, min((i + 1) * l, m)):
        (t, x, y) = txy[j]
        if t == 2:
            continue
        (x1, y1) = ((x - 1) % n + 1, (y - 1) % n + 1)
        (x2, y2) = (x % n + 1, y % n + 1)
        if x1 > y1:
            (x1, y1) = (y1, x1)
        if x2 > y2:
            (x2, y2) = (y2, x2)
        if (x1, y1) in e:
            e.remove((x1, y1))
            e1.add((x1, y1))
        if (x2, y2) in e:
            e.remove((x2, y2))
            e1.add((x2, y2))
    root = [i for i in range(n + 1)]
    rank = [1 for _ in range(n + 1)]
    for (u, v) in e:
        unite(u, v)
    cnt = defaultdict(lambda : 0)
    for (x, y) in e1:
        (u, v) = (get_root(x), get_root(y))
        if u > v:
            (u, v) = (v, u)
        cnt[u, v] += 1
        if cnt[u, v] == 1:
            G[u].add(v)
            G[v].add(u)
    for j in range(i * l, min((i + 1) * l, m)):
        (t, x, y) = txy[j]
        (x, y) = ((x + last - 1) % n + 1, (y + last - 1) % n + 1)
        if x > y:
            (x, y) = (y, x)
        (u, v) = (get_root(x), get_root(y))
        if u > v:
            (u, v) = (v, u)
        if t == 1:
            if not (x, y) in e1:
                e1.add((x, y))
                if u ^ v:
                    cnt[u, v] += 1
                    if cnt[u, v] == 1:
                        G[u].add(v)
                        G[v].add(u)
            else:
                e1.remove((x, y))
                if u ^ v:
                    cnt[u, v] -= 1
                    if not cnt[u, v]:
                        G[u].remove(v)
                        G[v].remove(u)
        else:
            ans0 = 1 if u == v or bfs(u, v, j) else 0
            ans.append(ans0)
            last = ans0
    for (x, y) in e1:
        (u, v) = (get_root(x), get_root(y))
        e.add((x, y))
        G[u].clear()
        G[v].clear()
sys.stdout.write(''.join(map(str, ans)))
from collections import defaultdict
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (rs, rt) = (get_root(s), get_root(t))
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        rank[rs] += 1
    if rank[s] >= rank[t]:
        root[rt] = rs
    else:
        root[rs] = rt
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False

def bfs(s, g, c):
    (q, k) = ([s], 0)
    color[s] = c
    while len(q) ^ k:
        i = q[k]
        for j in G[i]:
            if j == g:
                return True
            if color[j] ^ c:
                q.append(j)
                color[j] = c
        k += 1
    return False
(n, m) = map(int, input().split())
txy = [tuple(map(int, input().split())) for _ in range(m)]
l = 12345
e = set()
G = [set() for _ in range(n + 1)]
color = [-1] * (n + 1)
last = 0
ans = []
for i in range(m // l + min(m % l, 1)):
    e1 = set()
    for j in range(i * l, min((i + 1) * l, m)):
        (t, x, y) = txy[j]
        if t == 2:
            continue
        (x1, y1) = ((x - 1) % n + 1, (y - 1) % n + 1)
        (x2, y2) = (x % n + 1, y % n + 1)
        if x1 > y1:
            (x1, y1) = (y1, x1)
        if x2 > y2:
            (x2, y2) = (y2, x2)
        if (x1, y1) in e:
            e.remove((x1, y1))
            e1.add((x1, y1))
        if (x2, y2) in e:
            e.remove((x2, y2))
            e1.add((x2, y2))
    root = [i for i in range(n + 1)]
    rank = [1 for _ in range(n + 1)]
    for (u, v) in e:
        unite(u, v)
    cnt = defaultdict(lambda : 0)
    for (x, y) in e1:
        (u, v) = (get_root(x), get_root(y))
        if u > v:
            (u, v) = (v, u)
        cnt[u, v] += 1
        if cnt[u, v] == 1:
            G[u].add(v)
            G[v].add(u)
    for j in range(i * l, min((i + 1) * l, m)):
        (t, x, y) = txy[j]
        (x, y) = ((x + last - 1) % n + 1, (y + last - 1) % n + 1)
        if x > y:
            (x, y) = (y, x)
        (u, v) = (get_root(x), get_root(y))
        if u > v:
            (u, v) = (v, u)
        if t == 1:
            if not (x, y) in e1:
                e1.add((x, y))
                if u ^ v:
                    cnt[u, v] += 1
                    if cnt[u, v] == 1:
                        G[u].add(v)
                        G[v].add(u)
            else:
                e1.remove((x, y))
                if u ^ v:
                    cnt[u, v] -= 1
                    if not cnt[u, v]:
                        G[u].remove(v)
                        G[v].remove(u)
        else:
            ans0 = 1 if u == v or bfs(u, v, j) else 0
            ans.append(ans0)
            last = ans0
    for (x, y) in e1:
        (u, v) = (get_root(x), get_root(y))
        e.add((x, y))
        G[u].clear()
        G[v].clear()
sys.stdout.write(''.join(map(str, ans)))
from collections import defaultdict
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (rs, rt) = (get_root(s), get_root(t))
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        rank[rs] += 1
    if rank[s] >= rank[t]:
        root[rt] = rs
    else:
        root[rs] = rt
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False

def bfs(s, g, c):
    (q, k) = ([s], 0)
    color[s] = c
    while len(q) ^ k:
        i = q[k]
        for j in G[i]:
            if j == g:
                return True
            if color[j] ^ c:
                q.append(j)
                color[j] = c
        k += 1
    return False
(n, m) = map(int, input().split())
txy = [tuple(map(int, input().split())) for _ in range(m)]
l = 12345
e = set()
G = [set() for _ in range(n + 1)]
color = [-1] * (n + 1)
last = 0
ans = []
for i in range(m // l + min(m % l, 1)):
    e1 = set()
    for j in range(i * l, min((i + 1) * l, m)):
        (t, x, y) = txy[j]
        if t == 2:
            continue
        (x1, y1) = ((x - 1) % n + 1, (y - 1) % n + 1)
        (x2, y2) = (x % n + 1, y % n + 1)
        if x1 > y1:
            (x1, y1) = (y1, x1)
        if x2 > y2:
            (x2, y2) = (y2, x2)
        if (x1, y1) in e:
            e.remove((x1, y1))
            e1.add((x1, y1))
        if (x2, y2) in e:
            e.remove((x2, y2))
            e1.add((x2, y2))
    root = [i for i in range(n + 1)]
    rank = [1 for _ in range(n + 1)]
    for (u, v) in e:
        unite(u, v)
    cnt = defaultdict(lambda : 0)
    for (x, y) in e1:
        (u, v) = (get_root(x), get_root(y))
        if u > v:
            (u, v) = (v, u)
        cnt[u, v] += 1
        if cnt[u, v] == 1:
            G[u].add(v)
            G[v].add(u)
    for j in range(i * l, min((i + 1) * l, m)):
        (t, x, y) = txy[j]
        (x, y) = ((x + last - 1) % n + 1, (y + last - 1) % n + 1)
        if x > y:
            (x, y) = (y, x)
        (u, v) = (get_root(x), get_root(y))
        if u > v:
            (u, v) = (v, u)
        if t == 1:
            if not (x, y) in e1:
                e1.add((x, y))
                if u ^ v:
                    cnt[u, v] += 1
                    if cnt[u, v] == 1:
                        G[u].add(v)
                        G[v].add(u)
            else:
                e1.remove((x, y))
                if u ^ v:
                    cnt[u, v] -= 1
                    if not cnt[u, v]:
                        G[u].remove(v)
                        G[v].remove(u)
        else:
            ans0 = 1 if u == v or bfs(u, v, j) else 0
            ans.append(ans0)
            last = ans0
    for (x, y) in e1:
        (u, v) = (get_root(x), get_root(y))
        e.add((x, y))
        G[u].clear()
        G[v].clear()
sys.stdout.write(''.join(map(str, ans)))