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
#include <bits/stdc++.h>
using namespace std;

vector<int> o;
vector<int> m;
vector<int> k;
vector<int> pk;

void zo(int x) {
    if (o[x] != o[o[x]]) {
        zo(o[x]);
        o[x] = o[o[x]];
    }
    pk[x] = pk[o[x]];
}

bool czy(int a, int b) {
    if (o[a] == o[b]) {
        return 1;
    }
    return 0;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    o.resize(2*n+1, 0);
    m.resize(2*n+1, 0);
    k.resize(2*n+1, 0);
    pk.resize(2*n+1, 0);
    for (int i = 1; i < n+1; i++) {
        o[i] = i+n;
        o[i+n] = i+n;
        m[i+n] = 1;
        k[i+n] = 0;
    }
    for (int _ = 0; _ < q; _++) {
        char c;
        cin >> c;
        if (c == '?') {
            int d;
            cin >> d;
            zo(d);
            if (pk[d] == 0) {
                cout << 0;
            }
            else if (pk[d] == 1) {
                cout << '?';
            }
            else {
                cout << 1;
            }
        }
        else if (c == '-') {
            int c;
            cin >> c;
            zo(c);
            m[o[c]]--;
            k[o[c]]--;
            if (k[o[c]] == 0) {
                pk[o[c]] = 0;
            }
            o.push_back(o.size());
            m.push_back(1);
            k.push_back(0);
            pk.push_back(0);
            o[c] = o.size()-1;
            pk[c] = 0;
        }
        else {
            int a, b;
            cin >> a >> b;
            zo(a);
            zo(b);
            if (o[a] == o[b]) {
                k[o[a]]++;
                pk[o[a]] = 2;
            }
            else {
                if (m[o[a]] >= m[o[b]]) {
                    o[o[b]] = o[a];
                    k[o[a]] += k[o[b]]+1;
                    m[o[a]] += m[o[b]];
                    if (k[o[a]] == m[o[a]]) {
                        pk[o[a]] = 2;
                    }
                    else {
                        pk[o[a]] = 1;
                    }
                }
                else {
                    o[o[a]] = o[b];
                    k[o[b]] += k[o[a]]+1;
                    m[o[b]] += m[o[a]];
                    if (k[o[b]] == m[o[b]]) {
                        pk[o[b]] = 2;
                    }
                    else {
                        pk[o[b]] = 1;
                    }
                }
            }
        }
    }
}