1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class Node:
    def __init__(self, count, n):
        self.count = count
        self.n = n


def find(x, parent):
    if x != parent[x]:
        parent[x] = find(parent[x], parent)
    return parent[x]


def main(n, q, tak):
    queries = []
    for i in range(len(tak)):
        query = tak[i].split()
        if query[0] == '+':
            queries.append(['+', int(query[1]) - 1, int(query[2]) - 1])
        elif query[0] == '-':
            queries.append(['-', int(query[1]) - 1])
        else:
            queries.append(['?', int(query[1]) - 1])

    removed = [[] for _ in range(n)]
    count = n
    for query in queries[::-1]:
        count -= 1
        if query[0] == '-':
            removed[query[1]].append(count)

    ans = []
    sets = [Node(0, 1) for _ in range(n)]
    parent_set = [i for i in range(n)]

    for query in queries:
        if query[0] == '?':
            x = query[1]
            p_set = sets[find(x, parent_set)]
            if p_set.count == 0:
                ans.append('0')
            elif p_set.n == p_set.count:
                ans.append('1')
            else:
                ans.append('?')

        elif query[0] == '+':
            a, b = query[1], query[2]
            p_a, p_b = find(a, parent_set), find(b, parent_set)
            if p_a != p_b:
                if removed[p_a] and (not removed[p_b] or removed[p_a][-1] < removed[p_b][-1]):
                    sets[p_b].count += 1
                    parent_set[p_a] = p_b
                    sets[p_b].n += sets[p_a].n
                    sets[p_b].count += sets[p_a].count
                else:
                    sets[p_a].count += 1
                    parent_set[p_b] = p_a
                    sets[p_a].n += sets[p_b].n
                    sets[p_a].count += sets[p_b].count
            else:
                sets[p_a].count += 1
        else:
            x = query[1]
            removed[x].pop()
            p_x = find(x, parent_set)
            sets[p_x].count -= 1
            sets[p_x].n -= 1
            parent_set[x] = x
            sets[x] = Node(0, 1)

    print("".join(ans))


n, q = list(map(int, input().split()))
lines = []
for i in range(q):
    lines.append(input())

main(n, q, lines)