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
#include <iostream>
#include <vector>
using namespace std;

struct node{
    int rep;
    int mass;
    int state;
};


vector<int> vertex;
vector<node> fu;

void prepere(int n){
    fu.resize(n);
    vertex.resize(n);
    for(int i = 0; i < n; i++){
        fu[i] = {i, 1, 0};
        vertex[i] = i;
    }
}

int find(int v){
    if(fu[v].rep == v) return v;
    return fu[v].rep = find(fu[v].rep);
}

void validate(int a){
    if(fu[find(vertex[a])].state == 1){
        vertex[a] = fu.size();
        fu.push_back((node){fu.size(), 1, 0});
    }
}

void merge(int a, int b){
    validate(a);
    validate(b);

    a = find(vertex[a]);
    b = find(vertex[b]);

    if(a != b){
        if(fu[a].mass < fu[b].mass) swap(a, b);
        fu[b].rep = a;
        fu[a].mass += fu[b].mass;
    }
}

bool check(int a, int b){
    return find(vertex[a]) == find(vertex[b]);
}

char check_state(int v){
    if(fu[find(vertex[v])].state == 0) return '0';
    if(fu[find(vertex[v])].state == 1) return '1';
    if(fu[find(vertex[v])].mass < 2)   return '0';
    return '?';
}

void add_computer(int a, int b){
    if(check_state(a) != '1' && check_state(b) != '1' && !check(a, b)) {
        merge(a, b);
        fu[vertex[a]].state = 2;
        fu[vertex[b]].state = 2;   
        
        return;
    }

    merge(a, b);

    int rt = find(vertex[a]);
    fu[rt].state = 1;
}

void remove_computer(int a){
    fu[find(vertex[a])].mass--;
    vertex[a] = fu.size();
    fu.push_back((node){fu.size(), 1, 0});
}


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

    int n, q; cin >> n >> q;
    prepere(n);
    while(q--){
        char c; cin >> c;
        if(c == '+'){
            int a, b; cin >> a >> b;
            a--; b--;

            add_computer(a,b);

        }

        if(c == '-'){
            int a; cin >> a;
            a--;
            remove_computer(a);
        }

        if(c == '?'){
            int v; cin >> v;
            v--;
           cout << check_state(v);
        }

    }
    cout << endl;

    return 0;
}