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
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cassert>

using namespace std;

const int N = 3e5 + 7;
const int NN = 1e6 + 7;
vector<vector<int>> grupy;
int dsurep[NN], ile[NN], fancyrep[N], ilekomp[NN];

int find(int a) {
    if (dsurep[a] == a)
        return a;
    return dsurep[a] = find(dsurep[a]);
}

int onion(int a, int b) {
    a = find(a);
    b = find(b);

    if (a == b) {
        ilekomp[a]++;
        return a;
    }

    if (ile[a] < ile[b]) {
        swap(a, b);
    }

    dsurep[b] = a;
    ile[a] += ile[b];
    ilekomp[a] += ilekomp[b] + 1;
    grupy[a].insert(grupy[a].end(), grupy[b].begin(), grupy[b].end());

    return a;
}

void disjoin(int r) {
    assert(find(r) == r);
    for (auto it : grupy[r]) {
        dsurep[it] = it;
        ilekomp[it] = 1;
        ile[it] = 1;
        if (it != r) {
            grupy[it].clear();
            grupy[it].push_back(it);
        }
    }
    grupy[r].clear();
    grupy[r].push_back(r);
}

int remove(int a) {
    int r = find(a);
    if (ile[r] == 1) {
        ilekomp[a] = 0;
        return a;
    } else {
        ilekomp[r]--;
        ile[r]--;
        int nextfancy = grupy.size();
        grupy.emplace_back();
        grupy[nextfancy].push_back(nextfancy);
        dsurep[nextfancy] = nextfancy;
        ile[nextfancy] = 1;
        return nextfancy;
    }
}

int main() {
    int n, q;
    cin >> n >> q;
    grupy.emplace_back();

    for (int i = 1; i <= n; i++) {
        fancyrep[i] = i;
        dsurep[i] = i;
        ile[i] = 1;
        grupy.emplace_back();
        grupy[i].push_back(i);
    }

    string rodzaj;
    int x, y;
    while (q--) {
        cin >> rodzaj;
        if (rodzaj == "+") {
            cin >> x >> y;
            x = fancyrep[x];
            y = fancyrep[y];

            int r = onion(x, y);

            if (ilekomp[r] == ile[r]) {
                disjoin(r);
            }
        } else if (rodzaj == "-") {
            cin >> x;
            int fr = fancyrep[x];
            int nfr = remove(fr);
            fancyrep[x] = nfr;
        } else {
            cin >> x;
            x = fancyrep[x];
            x = find(x);
            if (ilekomp[x] == 0)
                cout << 0;
            else if (ilekomp[x] == ile[x])
                cout << 1;
            else
                cout << "?";
        }
    }

    return 0;
}