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
80
81
82
83
84
#include <iostream>
#include <vector>

const int MAXQ = 1000000+5;
const int MAXN = 300000+5;

struct Node {
    int p;
    int t;
    int s;
};

int I[MAXN];
int s = 1;
Node V[2*MAXQ];

int find(int i) {
    if (i == V[i].p) return i;
    V[i].p = find(V[i].p);
    return V[i].p;
}

void junion(int i, int j) {
    int vi = find(i);
    int vj = find(j);
    if (vi == vj) { V[vi].t = 1; return; }
    V[vj].t = std::max(V[vi].t, V[vj].t);
    V[vj].s = V[vi].s + V[vj].s;
    V[vi].p = vj;
}

void alloc(int e) {
    if (I[e] != 0) return;
    I[e] = s;
    V[s] = Node{.p = s, .t = 0, .s=1};
    ++s;
}

void add() {
    int a,b;
    std::cin >> a >> b;
    alloc(a);
    alloc(b);
    junion(I[a], I[b]);
}

void remove() {
    int c;
    std::cin >> c;
    int vi = find(I[c]);
    V[vi].s -= 1;
    I[c] = 0;
}

void query() {
    int d;
    std::cin >> d;
    if (I[d] == 0) std::cout << '0';
    else {
        int vi = find(I[d]);
        if (V[vi].s == 1 && V[vi].t == 0) std::cout << "0";
        else if (V[vi].t == 0) std::cout << "?";
        else std::cout << "1";
    }
}

int main() {
    std::ios_base::sync_with_stdio(0);
    int n, q;
    std::cin >> n >> q;
    V[0].t = -1;
    while (q--) {
        char c;
        std::cin >> c;
        switch (c) {
            case '+': add(); break;
            case '-': remove(); break;
            case '?': query(); break;
            default: std::clog << "wtf?" << std::endl; // wtf?
        }
    }
    std::cout << std::endl;
    return 0;
}