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

using namespace std;

typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define pb push_back
#define fi first
#define se second
#define rep(i,b,e) for(int i=(b); i<(e); i++)
#define each(a,x)  for(auto &a : (x))
#define all(x) (x).begin(), (x).end()
#define sz(x)  (int)(x).size()

struct DSU{
    vi par,cnt,cntPC;

    DSU(int n){
        n+=5;
        cnt.resize(n);
        par.resize(n);
        cntPC.resize(n);
        for(int i=0; i<n; ++i){
            par[i] = i;
            cnt[i] = 1;
            cntPC[i] = 0;
        }
    }

    int Find(int a){
        if(a!=par[a]) par[a] = Find(par[a]);
        return par[a];
    }

    bool Union(int a, int b){
        a = Find(a);
        b = Find(b);
        if(a==b) return false;
        if(cnt[a] < cnt[b]) swap(a,b);
        par[b] = a;
        cnt[a] += cnt[b];
        cntPC[a] += cntPC[b];
        return true;
    }
};

const int N = 1e6+4e5;
DSU dsu(N);
int rep[N],id;

void Remove(int v){
    int S = dsu.Find(rep[v]);
    dsu.cnt[S]--;
    dsu.cntPC[S]--;
    rep[v] = id++;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,q;
    cin >> n >> q;
    for(int i=0; i<=n+5; ++i)
        rep[i] = i;
    id = n+10;
    while(q--){
        char c;
        cin >> c;
        if(c=='+'){
            int a,b;
            cin >> a >> b;
            a = rep[a];
            b = rep[b];
            dsu.Union(a,b);
            int S = dsu.Find(a);
            ++dsu.cntPC[S];
        }else if(c=='-'){
            int a;
            cin >> a;
            Remove(a);
        }else{
            int a;
            cin >> a;
            a = rep[a];
            int S = dsu.Find(a);
            // cout << "CNT:" << dsu.cnt[S] << endl;
            // cout << "CNTPc:" << dsu.cntPC[S] << endl;
            if(dsu.cnt[S]==dsu.cntPC[S]) cout << 1;
            else if(dsu.cntPC[S]>0) cout << "?";
            else cout << 0;
        }
    }
    return 0;
}