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

int const N = 3e5+3, M = 1e6+N;
int n, q, mx, rep[M], amt[M], edges[M];
string ans;
unordered_map <int, int> m;

int find(int x){
    return (rep[x] == x ? x : rep[x] = find(rep[x]));
}

void unite(int x, int y){
    if(x == y){
        edges[x] += 1;
        return;
    } 
    if(amt[x] < amt[y]) swap(x, y);
    amt[x] += amt[y];
    edges[x] += edges[y] + 1;
    rep[y] = x;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; ++i) amt[i] = 1, rep[i] = i, m[i] = i;
    mx = n+1;
    for(int i = 1, a, b; i <= q; ++i){
        char type; cin >> type >> a;
        if(type == '+'){
            cin >> b;
            unite(find(m[a]), find(m[b]));
        }
        if(type == '-'){
            b = find(m[a]);
            edges[b] -= 1;
            amt[b] -= 1;
            m[a] = mx++;
            amt[m[a]] = 1;
            rep[m[a]] = m[a];
        }
        if(type == '?'){
            int b = find(m[a]);
            if(edges[b] >= amt[b]) ans.push_back('1');
            else if(edges[b] == 0) ans.push_back('0');
            else ans.push_back('?');
        }
    }
    cout << ans;
}