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
#include<bits/stdc++.h>
using namespace std;
const int s1 = 300'001;
const int s2 = 500'001;

vector<int>prz[s1];
int uf[s1];
int uf_size[s1];

int computer[s1];
//0 - nie ma, 1 - mozliwe ze ma, 2 - ma
int findd(int a){
    if (uf[a] == a|| uf[a] == 0) return a;
    else return findd(uf[a]);
}
void unionn(int a, int b){
    int f_a = findd(a);
    int f_b = findd(b);
    if (computer[f_b] == 2) computer[f_a] = true;
    else if(computer[f_b] == 1 && computer[f_a] != 2) computer[f_a] = 1;
    uf[f_a] = f_b;
    uf_size[f_a] += uf_size[f_b];
    prz[f_b].push_back(f_a);
}
void add(int a, int b){
    int f_a = findd(a);
    int f_b = findd(b);
    if (f_a == f_b){
        computer[f_a] = 2;
    }
    else{
        computer[f_a] = 1;
        computer[f_b] = 1;
        unionn(f_a, f_b);
    }  
}
void remove(int a){
    int f_a = findd(a);
    int comp = computer[f_a];
    int sizee = uf_size[f_a];
    if (f_a == a){
        for (int i : prz[f_a]){
            if (a == uf[i]){
                f_a = i;
                uf_size[f_a] = uf_size[a] - 1;
                break;
            }
        }
    }
    for (int i : prz[a]){
        if(uf[i] == a){
            uf[i] = f_a;
        } 
    }
    computer[f_a] = comp;
    uf_size[f_a] = sizee;
    if (uf_size[f_a] == 1 && computer[f_a] == 1){
        computer[f_a] = 0;
    }
    uf[a] = a;
    uf_size[a] = 1;
    computer[a] = 0;
    
}
string q(int a){
    int f_a = findd(a);
    if (computer[f_a] == 0) return "0";
    if (computer[f_a] == 2) return "1";
    return "?"; 
}
void f() {
    int n, m;
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        uf[i] = i;
        uf_size[i] = 1;
    }
    for (int i = 0; i < m; i++){
        char operation;
        int x, y;
        cin >> operation;
        if (operation == '+'){
            cin >> x >> y;
            add(x, y);
        }
        else if (operation == '-'){
            cin >> x;
            remove(x);
        }
        else {
            cin >> x;
            cout << q(x);
        }
    }    
    return;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    f();
    return 0;
}