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
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 3e5+5;
int n, q, lst, nw[maxn];
unordered_map<int, bool> iscyk;
unordered_map<int, int> rep, siz;

int f(int a){
	if (rep[a] == 0)
		return rep[a] = a;
	if (rep[a] == a)
		return a;
	return rep[a] = f(rep[a]);
}

void un(int a, int b){
	a = f(nw[a]);
	b = f(nw[b]);
	if (a == b){
		iscyk[a] = 1;
		return;
	}
        if (iscyk[a] || iscyk[b])
                iscyk[a] = iscyk[b] = 1;
	rep[a] = b;
	siz[b] += siz[a];
}

void dl(int a){
	--siz[f(nw[a])];
	nw[a] = ++lst;
	rep[nw[a]] = nw[a];
	siz[nw[a]] = 1;
}

void sp(int a){
	if (iscyk[f(nw[a])])
		cout << 1;
	else if (siz[f(nw[a])] == 1)
		cout << 0;
	else
		cout << '?';
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; ++i){
		rep[i] = i;
		nw[i] = i;
		siz[i] = 1;
	}
	lst = n;
	char c;
	int a, b;
	while (q--){
		cin >> c;
		if (c == '+'){
			cin >> a >> b;
			un(a,b);
		}
		if (c == '-'){
			cin >> a;
			dl(a);
		}
		if (c == '?'){
			cin >> a;
			sp(a);
		}
	}
}