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
97
98
#include<bits/stdc++.h>
#include<unordered_set>
using namespace std;
#define SIZE int(3e5 + 1)
unordered_set<int> uni[int(1e6)];
int unk[SIZE];
int val[SIZE];
int n, q, a, b, ind;
char c;
string ans;
void explode (int y) {
    for (int item : uni[y]) {
        unk[item] = 1;
    }  
    uni[y].clear();
}
void singleUpdate (int x) {
    if (!unk[x]) {
        unk[x] = 1;
    } else {
        explode(val[x]);
    }
}
void doubleUpdate (int x1, int y1) {
    if (unk[x1]==1) {
        singleUpdate(y1);
    } else if (unk[y1]==1) {
        singleUpdate(x1);
    } else if ((!unk[x1]) && (!unk[y1])) {
        unk[x1] = 2;
        unk[y1] = 2;
        val[x1] = ind;
        val[y1] = ind;
        uni[ind].insert(x1);
        uni[ind].insert(y1);
        ind++;
    } else if ((!unk[x1]) || (!unk[y1])) {
        if (!unk[x1]) {
            unk[x1] = 2;
            val[x1] = val[y1];
            uni[val[x1]].insert(x1);
        } else {
            unk[y1] = 2;
            val[y1] = val[x1];
            uni[val[y1]].insert(y1);
        }
    } else {
        if (val[x1] == val[y1]) {
            explode(val[x1]);
        } else {
            if (uni[val[x1]].size() < uni[val[y1]].size()) {
                for (int item : uni[val[x1]]) {
                    uni[val[y1]].insert(item);
                    val[item] = val[y1];
                }
                uni[val[x1]].clear();
            } else {
                for (int item : uni[val[y1]]) {
                    uni[val[x1]].insert(item);
                    val[item] = val[x1];
                }
                uni[val[y1]].clear();
            }
        }
    }
}
int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> q;
    for (int i = 0; i < q; i++) {
        cin >> c;
        if (c == '+') {
            cin >> a >> b;
            if (a==b) {
                singleUpdate(a);
            } else {
                doubleUpdate(a, b);
            }
        } else if (c == '-') {
            cin >> a;
            if (unk[a] == 2) {
                uni[val[a]].erase(a);
            }
            unk[a] = 0;
        } else {
            cin >> a;
            if (unk[a] == 2) {
                ans.push_back('?');
            } else {
                ans.push_back(unk[a]+48);
            }
        }
    }
    cout << ans << endl;
    return 0;
}