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

using namespace std;

vector<int> rep;
vector<int> cnt;
vector<int> wrapper;
int rep_count;

const int iscomp = 0;

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

void uni(int a, int b){
    a = find(a);
    b = find(b);
    if(a!=b){
        if(cnt[a] < cnt[b]) swap(a,b);
        rep[b] = a;
        cnt[a]+=cnt[b];
    }
}

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

    int n,q;
    cin>>n>>q;
    rep.resize(n+1+q);
    wrapper.resize(n+1);
    for(int i=0;i<=n+q;++i) rep[i] = i;
    for(int i=0;i<=n;++i) wrapper[i] = i;
    rep_count = n;
    cnt.assign(n+1+q, 1);

    cnt[0] = 1'000'000'00;

    while(q--){
        char type; cin>>type;
        if(type== '+'){
            int a,b; cin>>a>>b;
            a = wrapper[a];
            b = wrapper[b];
            if(find(a) == find(b)){
                uni(0,a);
            }
            else{
                uni(a,b);
            }
        }
        if(type == '-'){
            int a; cin>>a;
            cnt[find(wrapper[a])]--;
            // cout<< "\nCNT "<< find(a) << " SMALLER AND NOW" << cnt[find(a)]<<'\n';
            wrapper[a] = ++rep_count;
        }
        if(type == '?'){
            int a; cin>>a;
            a = find(wrapper[a]);
            if(a == 0) cout<<1;
            else if(cnt[a]>1) cout<<'?';
            else cout<<0;
            
        }
    }
    
}