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
#include<cstdio>
#include<algorithm>
#define S 2000007

using namespace std;

int R[S];
int roz[S];
int edges[S];
int nodes[S];

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

void Union(int a, int b){
    a = Find(a);
    b = Find(b);
    if(a != b){
        if(roz[a] < roz[b])
            swap(a,b);
        roz[a] += roz[b];
        R[b] = a;
        edges[a] += edges[b];
        nodes[a] += nodes[b];
        edges[a]++;
    } else {
        edges[a]++;
    }
}

int main(void){
    int n,q;
    scanf("%d %d",&n,&q);
    for(int i = 1; i <= n; i++){
        roz[i] = 1;
        R[i] = i+n;
        roz[i+n] = 2;
        R[i+n] = i+n;
        nodes[i] = 1;
        nodes[i+n] = 1;
    }
    int id = 2*n;
    for(int i = 1; i <= q; i++){
        char c;
        scanf(" %c", &c);
        if(c == '+'){
            int a,b;
            scanf("%d %d",&a,&b);
            Union(a,b);
        }else if(c == '-'){
            int a;
            scanf("%d", &a);
            int p = Find(a);
            nodes[p]--;
            edges[p]--;
            roz[p]--;

            id++;
            roz[id] = 2;
            R[id] = id;
            R[a] = id;
            roz[a] = 1;
            nodes[id] = 1;
        }else{
            int a;
            scanf("%d", &a);
            int p = Find(a);
            if(edges[p] == 0){
                printf("0");
            }else if(edges[p] == nodes[p]){
                printf("1");
            }else{
                printf("?");
            }
        }
    }
    printf("\n");

    return 0;
}