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
#include <bits/stdc++.h>
#define scanf(...) scanf(__VA_ARGS__)?:0
using namespace std;

int n, q;
int skl[300005], poz[300005];
vector<int> s[300005];
int zajeta[300005];
vector<int> wolne;

int main() {
	scanf("%d%d", &n, &q);
	for (int i=1; i<=n; i++) {
		skl[i] = i;
		s[i].push_back(i);
	}
	wolne.push_back(n+1);
	
	for (int i=0; i<q; i++) {
		char z;
		scanf(" %c", &z);
		if (z == '+') {
			int a, b;
			scanf("%d%d", &a, &b);
			if (skl[a] == skl[b]) zajeta[skl[a]] = 1;
			else {
				int s1 = skl[a], s2 = skl[b];
				if (s[s1].size() < s[s2].size()) {
					for (int i: s[s1]) {
						skl[i] = s2;
						poz[i] = s[s2].size();
						s[s2].push_back(i);
					}
					s[s1].clear();
					wolne.push_back(s1);
					if (zajeta[s1]) zajeta[s2] = 1;
					zajeta[s1] = 0;
				} else {
					for (int i: s[s2]) {
						skl[i] = s1;
						poz[i] = s[s1].size();
						s[s1].push_back(i);
					}
					s[s2].clear();
					wolne.push_back(s2);
					if (zajeta[s2]) zajeta[s1] = 1;
					zajeta[s2] = 0;
				}
			}
		} else {
			int c;
			scanf("%d", &c);
			if (z == '-') {
				int s1 = skl[c];
				if ((int) s[s1].size() > 1) {
					int num = s[s1].back();
					poz[num] = poz[c];
					swap(s[s1][poz[c]], s[s1].back());
					s[s1].pop_back();
					skl[c] = wolne.back();
					wolne.pop_back();
					s[skl[c]].push_back(c);
					poz[c] = 0;
					zajeta[skl[c]] = 0;
				} else {
					zajeta[s1] = 0;
				}
			} else {
				if (zajeta[skl[c]]) putchar('1');
				else if ((int) s[skl[c]].size() == 1) putchar('0');
				else putchar('?');
			}
		}
	}
	puts("");
}