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
//GRT_2018
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define all(x) x.begin(), x.end()
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 300 * 1000 + 10, qax = 1000 * 1000 + 10;
int n, q;

int p[nax + qax];
vi con[nax + qax];
int id[nax + qax];
int rev[nax + qax];
bool active[nax + qax];
bool black[nax + qax];

bool Onion(int a, int b) {
    a = p[a];
    b = p[b];
    if (a == b) return false;
    if ((int)con[a].size() < (int)con[b].size()) {
        swap(a, b);
    }
    for (int x : con[b]) {
        con[a].PB(x);
        p[x] = a;
    }
    con[b].clear();
    return true;
}

int nr;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
    cin >> n >> q;
    nr = n;
    for (int i = 1; i <= n; ++i) {
        id[i] = i;
        rev[i] = i;
        p[i] = i;
        con[i] = {i};
        black[i] = false;
        active[i] = true;
    }
    while (q--) {
        char typ;
        cin >> typ;

        if (typ == '+') {
            int a, b;
            cin >> a >> b;
            a = id[a];
            b = id[b];
            if (black[a] || black[b] || !Onion(a, b)) {
                if (black[a]) swap(a, b);
                for (int x : con[p[a]]) {
                    if (active[x]) {
                        active[x] = false;
                        int y = rev[x];
                        nr++;
                        id[y] = nr;
                        rev[nr] = y;
                        p[nr] = nr;
                        con[nr] = {nr};
                        black[nr] = true;
                        active[nr] = true;
                    }
                }
            }
        } else if (typ == '-') {
            int c;
            cin >> c;
            c = id[c];

            if (black[c]) black[c] = false;
            else {
                active[c] = false;
                int y = rev[c];
                nr++;
                id[y] = nr;
                rev[nr] = y;
                p[nr] = nr;
                con[nr] = {nr};
                black[nr] = false;
                active[nr] = true;
            }

        } else {
            int d;
            cin >> d;
            d = id[d];

            if (black[d]) cout << "1";
            else {
                vi good = {};
                while (!con[p[d]].empty()) {
                    int x = con[p[d]].back();
                    con[p[d]].pop_back();
                    if (active[x]) good.PB(x);
                    if ((int)good.size() >= 2) break;
                }
                for (int x : good) con[p[d]].PB(x);
                if ((int)con[p[d]].size() == 1) cout << "0";
                else cout << "?";
            }
        }
    }
}