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

typedef enum { NEG, HALF, POS } state;

struct node{
    node* rep;
    state stan;
    int computers;
    int members;

    node() {
        rep = this;
        stan = NEG;
        computers = 0;
        members = 1;
    }

    node* Find(){
        return (rep == this ? rep : rep = (rep -> Find()));        
    }

    void Union(node* B){
        B = B -> Find();
        node* A = this -> Find();

        (A -> computers)++;

        if(A != B){
            (B -> rep) = A;
            (A -> members) += (B -> members);
            (A -> computers) += (B -> computers);
        }

        if(A -> computers == A -> members) (A -> stan) = POS;
        else (A -> stan) = HALF;
    }

    char ans(){
        if (stan == NEG) return '0';
        if (stan == POS) return '1';
        return '?';
    }
};

const int MAXN = 3 * 1e5 + 7;

node* tab[MAXN];


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

    int n, q;
    cin >> n >> q;

    for(int i = 1; i <= n; i++){
        tab[i] = new node;
    }

    char c;
    int x, y;

    string odp = "";

    node* pom;

    for(int i = 0; i < q; i++){
        cin >> c;

        if(c == '?'){
            cin >> x;

            odp += ((tab[x] -> Find()) -> ans());
        }

        if(c == '+'){
            cin >> x >> y;

            tab[x] -> Union(tab[y]);            
        }

        if(c == '-'){
            cin >> x;
        
            pom = tab[x] -> Find();
            (pom -> computers)--;
            (pom -> members)--;

            if((pom -> computers) == 0) (pom -> stan) = NEG;
            
            tab[x] = new node;
        }

/*        for(int t = 1; t <= n; t++){
            cout << t << ": " << tab[t] << " " << tab[t] -> rep << " " << tab[t] -> computers << " " << tab[t] -> members << " " << tab[t] -> stan << endl;
        }
        cout << endl;*/
    }

    cout << odp << endl;

    return 0;
}