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
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#define dassert assert
#else
#define debug(...)
#define dassert(x)
#endif

#define x first
#define y second
#define ir(a, x, b) ((a) <= (x) && (x) <= (b))
#define vec vector
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(), (x).end()

using ll = long long;


struct dsu {
    int n;
    vec<int> over, sz, tag;
    dsu() {}
    dsu(int n_) : n(n_), over(n), sz(n, 1), tag(n, 0) {
        iota(all(over), 0);
    }
    
    int find(int x) {
        if (over[x] == x) {
            return x;
        }
        return over[x] = find(over[x]);
    }
    
    void unify(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return;
        if (sz[x] < sz[y]) swap(x, y); // sz[x] >= sz[y]
        sz[x] += sz[y];
        tag[x] += tag[y];
        over[y] = over[x];
    }
};

int n;
dsu d;
vec<int> ptr;
vec<int> inv;
vec<bool> sure;
vec<vec<int>> g;
void overwrite(int v) {
    int a = inv[v];
    debug(v, a, n);
    inv[v] = -1;
    ptr[a] = n;
    d.tag.push_back(0); dassert(d.tag.size() == n+1);
    d.sz.push_back(1); dassert(d.sz.size() == n+1);
    d.over.push_back(n); dassert(d.over.size() == n+1);
    inv.push_back(a); dassert(inv.size() == n+1);
    g.push_back({});
    dassert(inv[ptr[a]] == a);
    n++;
}

void collapse(int v, int p) {
    debug(v, p);
    if (inv[v] != -1) {
        sure[inv[v]] = true;
        overwrite(v);
    }
    for (auto c : g[v]) {
        if (c == p) continue;
        collapse(c, v);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int q;
    cin >> n >> q;
    ptr.resize(n); iota(all(ptr), 0);
    sure.resize(n);
    inv.resize(n); iota(all(inv), 0);
    g.resize(n);
    d = dsu(n);
    while (q--) {
        char c;
        cin >> c;
        debug(c);
        if (c == '+') {
            int a, b; cin >> a >> b; --a, --b;
            if (sure[a]) {
                collapse(ptr[b], ptr[b]);
                continue;
            }
            if (sure[b]) {
                collapse(ptr[a], ptr[a]);
                continue;
            }
            
            if (d.find(ptr[a]) == d.find(ptr[b])) {
                collapse(ptr[a], ptr[a]);
            } else {
                g[ptr[a]].push_back(ptr[b]);
                g[ptr[b]].push_back(ptr[a]);
                d.unify(ptr[a], ptr[b]);
            }
        } else if (c == '-') {
            int a; cin >> a; --a;
            sure[a] = 0;
            d.tag[d.find(ptr[a])]++;
            overwrite(ptr[a]);
        } else {
            int a; cin >> a; --a;
            if (sure[a]) {
                cout << "1";
            } else if (d.tag[d.find(ptr[a])]+1 == d.sz[d.find(ptr[a])]) {
                cout << "0";
            } else {
                cout << "?";
            }
        }
    }
    cout << "\n";
    return 0;
}