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
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;
const int N = 300005;

int parent[N], type[N], n, q, i, a, b, c, d, newL;
char t[3];
set<int> v[N];
VI vv;

void makeSet(int a) {
    parent[a] = a;
	v[a].insert(a);
	type[a] = 0;
}
 
void Union(int a, int b) {
	int newType = max(type[a], type[b]);
    if (v[a].size() >= v[b].size()) {
		for (auto& w : v[b]) {
			v[a].insert(w);
			parent[w] = a;
		}
		v[b].clear();
		type[a] = newType;
	} else {
		for (auto& w : v[a]) {
			v[b].insert(w);
			parent[w] = b;
		}
		v[a].clear();
		type[b] = newType;
	}
}


int main() {
srand(time(0));
scanf("%d %d", &n, &q);
for (i=1;i<=n;i++) makeSet(i);
while (q--) {
	scanf("%s", t);
	if (t[0] == '+') {
		scanf("%d %d", &a, &b);
		c = parent[a];
		d = parent[b];
		if (c == d) type[c] = 1; else Union(c, d);
	} else if (t[0] == '-') {
		scanf("%d", &a);
		c = parent[a];
		if (c != a) {
			makeSet(a);
			v[c].erase(a);
		} else if (v[c].size() == 1) {
			type[a] = 0;
		} else {
			vv.clear();
			for (auto& w : v[c]) if (w != a) vv.pb(w);
			v[c].clear();
			newL = vv[rand() % vv.size()];
			type[newL] = type[c];
			makeSet(a);
			for (auto& w : vv) {
				parent[w] = newL;
				v[newL].insert(w);
			}
		}
	} else {
		scanf("%d", &a);		
		c = parent[a];
		//printf("%d %d %d %d\n", a, c, v[c].size(), type[c]);
		if (v[c].size() == 1 && type[c] == 0) printf("0"); else if (type[c] == 1) printf("1"); else printf("?");
	}
}
printf("\n");
return 0;
}