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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6+7;
struct dsu{
	int P[N];
	int clp[N],dead[N],sz[N];
	int ptr;
	dsu(){
		ptr = 0;
	}
	int create_node(){
		ptr += 1;
		P[ptr] = ptr;
		clp[ptr] = 0;
		dead[ptr] = 0;
		sz[ptr] = 1;
		return ptr;
	}
	int F(int x){
		if (x==P[x]){
			return x;
		}
		return P[x] = F(P[x]);
	}
	void unite(int a,int b){
		a = F(a);
		b = F(b);
		if (a==b){
			clp[a] = 2;
			return;
		}
		sz[b] += sz[a];
		dead[b] += dead[a];
		clp[b] = max(clp[a],clp[b]);
		clp[b] = max(clp[b],1);
		P[a] = b;
	}
	int pcol(int a){
		int par = F(a);
		if (clp[par]==1 and sz[par]-dead[par]==1){
			return 0;
		}
		return clp[F(a)];
	}
	void kill(int a){
		dead[F(a)] += 1;
	}
} D;
int Place[N];
void solve(){
	int n,q;
	cin>>n>>q;
	for(int i = 1;i<=n;i+=1){
		Place[i] = D.create_node();
	}
	for(int i = 1;i<=q;i+=1){
		char type;
		cin>>type;
		if (type=='?'){
			int x;
			cin>>x;
			int col = D.pcol(Place[x]);
			if (col==0){
				cout<<"0";
			}
			if (col==1){
				cout<<"?";
			}
			if (col==2){
				cout<<"1";
			}
		}
		if (type=='+'){
			int a,b;
			cin>>a>>b;
			D.unite(Place[a],Place[b]);
		}
		if (type=='-'){
			int x;
			cin>>x;
			D.kill(Place[x]);
			Place[x] = D.create_node();
		}
	}
	cout<<'\n';
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	solve();
	return 0;
}