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

//#define ALERT() do{cerr << "[" << __LINE__ << "] Something went wrong.\n";}while(0)
#define ALERT() do{}while(0)

int constexpr N = 300'010;
int constexpr X = 1'300'010;
enum { ROOT = -1234567 };

enum { ALPHA = 1, OMEGA = 2 };
inline int kombajn(int a, int b) {
    if(a == ALPHA && b == OMEGA) return ALPHA;
    else if(a == OMEGA && b == ALPHA) return ALPHA;
    else if(a == OMEGA && b == OMEGA) return OMEGA;
    else { ALERT(); return 0; }
}

int n, q;
int phi[N];


int Size[X];
int Parent[X];
int Type[X];
int Dead[X];

int vertex_count = 0;
inline int vertex_new() {
    ++vertex_count;
    Size[vertex_count] = 1;
    Parent[vertex_count] = ROOT;
    Type[vertex_count] = OMEGA;
    Dead[vertex_count] = 0;
    return vertex_count;
}

/*void debaguj(int i) {
    cout << "(";
    cout << i << ", ";
    int u = phi[i];
    cout << u << ", ";
    while(Parent[u] != ROOT) u = Parent[u];
    cout << u << ", ";
    cout << Size[u] << ", ";
    if(Type[u] == ALPHA) cout << "alpha, ";
    else if(Type[u] == OMEGA) cout << "omega, ";
    else { ALERT(); }
    cout << Dead[u] << ")\n";
    cout.flush();
}*/

void dostarczyc(int i, int j) {
    int u = phi[i];
    int v = phi[j];
    while(Parent[u] != ROOT) u = Parent[u];
    while(Parent[v] != ROOT) v = Parent[v];
    if(u == v) {
        if(Type[u] == OMEGA) Type[u] = ALPHA;
        else { ALERT(); }
    } else {
        if(Size[u] < Size[v]) swap(u, v);
        Size[u] += Size[v];
        Parent[v] = u;
        Type[u] = kombajn(Type[u], Type[v]);
        Dead[u] += Dead[v];
    }
}

void zepsuc(int i) {
    int u = phi[i];
    while(Parent[u] != ROOT) u = Parent[u];
    ++Dead[u];
    phi[i] = vertex_new();
}

char stwierdzic(int i) {
    int u = phi[i];
    while(Parent[u] != ROOT) u = Parent[u];
    if(Type[u] == ALPHA) return '1';
    else if(Type[u] == OMEGA) {
        if(Dead[u] == Size[u] - 1) return '0';
        else return '?';
    } else { ALERT(); return 'a'; }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> q;
    for(int i = 1; i <= n; ++i)
        phi[i] = vertex_new();


    while(q--) {
        char c;
        cin >> c;
        switch(c) {
            case '+': { int a, b; cin >> a >> b; dostarczyc(a, b);      } break;
            case '-': { int c;    cin >> c;      zepsuc(c);             } break;
            case '?': { int d;    cin >> d;      cout << stwierdzic(d); } break;
        }
        /*for(int i = 1; i <= n; ++i)
            debaguj(i);
        cout << "\n";*/
    }
    cout << '\n';

    return 0;
}