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>

#define ll long long
#define fors(u, n, s) for(ll u = (s); u < (n); u++)
#define foru(u, n) fors(u, n, 0)
#define vec vector
#define pb push_back
#define f first
#define s second
#define ir(a, b, x) (((a) <= (x)) && ((x) <= (b)))
#define pint pair<ll, ll>

using namespace std;

const int N = 4e5;
const int Q = 2e6;
int n;
int q;

bool is_complete[N+Q];
int dsu[N+Q];
int rnk[N+Q];
int sz[N+Q];

int get_parent(int x){
    if (dsu[x] == x) return x;
    dsu[x] = get_parent(dsu[x]);
    return dsu[x];
}

void mrg(int x, int y) {
    x = get_parent(x); y = get_parent(y);
    if(x == y) {
        is_complete[x] = true;
    } else {
        if (rnk[x] < rnk[y]) swap(x, y);
        if (rnk[x] == rnk[y]) rnk[x] ++;
        dsu[y] = x;
        sz[x] += sz[y];
        is_complete[x] = is_complete[x] || is_complete[y];
    }
}

int my_set[N];

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

    foru(i, N+Q) dsu[i]=i;
    foru(i, N+Q) sz[i]=1;

    cin >> n >> q;

    int alloc = 0;

    foru(i, n) {my_set[i]=alloc; alloc++;}

    foru(_i, q) {
        char c; cin >> c;
        if (c == '+') {
            int x; int y; cin >> x >> y; x--; y--;

            mrg(my_set[x], my_set[y]);

        } else if (c == '-'){
            int x; cin >> x; x--;
            sz[get_parent(my_set[x])] --;
            my_set[x]=alloc; alloc++;
        } else if (c == '?'){
            int x; cin >> x; x--;
            if(is_complete[get_parent(my_set[x])]) cout << "1";
            else if (sz[get_parent(my_set[x])] == 1) cout << "0";
            else cout << "?";
        }
    }

    return 0;
}