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

constexpr int maxn = 3e5 + 7, maxnq = 2e6 + 7;
int n, q;
bool musiMiec[maxnq], musiNieMiec[maxnq];
int rep[maxnq], newNumber[maxn], cntTaken[maxnq], members[maxnq];
std::vector<int> graf[maxn * 4];

void init() {
    for(int i = 1; i <= n; i++) {
        newNumber[i] = i;
        rep[i] = i;
        musiNieMiec[i] = true;
        members[i] = 1;
    }
}

int fuFind(int x) {
    if(rep[x] == x)
        return x;
    rep[x] = fuFind(rep[x]);
    return rep[x];
}
void fuUnion(int x, int y) {
    x = fuFind(x); y = fuFind(y);
    if(x == y)
        return;
    rep[x] = y;
    members[y] += members[x];
    cntTaken[y] += cntTaken[x];
}

void chk(int v) {
    if(cntTaken[fuFind(v)] + 1 != members[fuFind(v)] || musiNieMiec[v] || musiMiec[v])
        return;
    musiNieMiec[v] = true;
    musiMiec[v] = false;
    graf[v].clear();
    rep[v] = v;
    members[v] = 1;
    cntTaken[v] = 0;
}

void daj(int v) {
    rep[v] = v;
    musiMiec[v] = true;
    musiNieMiec[v] = false;
    for(const auto& u : graf[v]) {
        if(rep[u] == u)
            continue;
        daj(u);
    }
    graf[v].clear();
}
void add(int a, int b) {
    chk(a); chk(b);
    if(fuFind(a) == fuFind(b) || musiMiec[b]) {
        daj(fuFind(a));
    }
    if(musiMiec[a]) {
        daj(fuFind(b));
    }
    musiNieMiec[a] = false;
    musiNieMiec[b] = false;
    graf[a].push_back(b);
    graf[b].push_back(a);
    fuUnion(a, b);
}

void query(int v) {
    chk(v);
    printf(musiMiec[v] ? "1" : musiNieMiec[v] ? "0" : "?");
}

void take(int v) {
    auto vv = newNumber[v];
    cntTaken[fuFind(vv)]++;
    musiNieMiec[vv] = true;
    musiMiec[vv] = false;

    newNumber[v] = ++n;
    musiNieMiec[n] = true;
    musiMiec[n] = false;
    rep[n] = n;
    members[n] = 1;
}

int main() {
    scanf("%d%d", &n, &q);
    init();
    char c;
    int a, b;
    for(int i = 0; i < q; i++) {
        scanf(" %c", &c);
        if(c == '+') {
            scanf("%d%d", &a, &b);
            add(newNumber[a], newNumber[b]);
        }
        if(c == '-') {
            scanf("%d", &a);
            take(a);
        }
        if(c == '?') {
            scanf("%d", &a);
            query(newNumber[a]);
        }
    }
    return 0;
}