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

using namespace std;

vector<int> parent;
int representative[300001];
vector<int> S;
vector<bool> marked;

int Find(int x){
    if(parent[x]==x) return x;
    parent[x]=Find(parent[x]);
    return parent[x];
}

void Union(int x, int y){
    x=Find(x);
    y=Find(y);
    if(x==y){
        marked[x]=true;
        return;
    }
    
    if(S[x]>S[y]){
        marked[x]=(marked[x] || marked[y]);
        S[x]+=S[y];
        parent[y]=x;
    }
    else{
        marked[y]=(marked[x] || marked[y]);
        S[y]+=S[x];
        parent[x]=y;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n, q;
    cin>>n>>q;
    
    int a, b;
    char c;
    
    for(int i=0; i<=n; i++){
        parent.emplace_back(i);
        S.emplace_back(1);
        marked.emplace_back(false);
        representative[i]=i;
    }
    
    for(int i=0; i<q; i++){
        cin>>c;
        if(c=='?'){
            cin>>a;
            a=representative[a];
            int x=Find(a);
            if(marked[x]) cout<<1;
            else if(S[x]==1) cout<<0;
            else cout<<'?';
        }
        else if(c=='+'){
            cin>>a>>b;
            Union(representative[a], representative[b]);
        }
        else{
            cin>>a;
            S[Find(representative[a])]--;
            representative[a]=parent.size();
            parent.push_back(parent.size());
            S.push_back(1);
            marked.push_back(false);
        }
    }
    
    return 0;
}