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

int nowy[300001];
int par[2000001];
int s_size[2000001];
bool rodzaj[2000001];
int FIND(int x){
	if (par[x] == x) return x;
	return par[x] = FIND(par[x]);
}
void UNION(int x, int y){
	int a = FIND(x);
	int b = FIND(y);
	if (a == b){
		rodzaj[a] = 1;
		return;
	}
	if (s_size[a] > s_size[b]) swap(a,b);
	par[a] = b;
	s_size[b] += s_size[a];
	rodzaj[b] |= rodzaj[a];
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int i;
	int n,q;
	cin>>n>>q;
	for (i = 1; i <= n; i++){
		par[i] = i;
		s_size[i] = 1;
		nowy[i] = i;
	}
	int pt = n+1;
	string wy;
	while (q--){
		char c;
		cin>>c;
		if (c == '+'){
			int a,b;
			cin>>a>>b;
			a = nowy[a];
			b = nowy[b];
			UNION(a,b);
		}else if (c == '-'){
			int x;
			cin>>x;
			s_size[FIND(nowy[x])]--;
			nowy[x] = pt;
			par[pt] = pt;
			s_size[pt] = 1;
			pt++;
		}else{
			int x;
			cin>>x;
			x = nowy[x];
			if (rodzaj[FIND(x)]) wy += '1';
			else if (s_size[FIND(x)] == 1) wy += '0';
			else wy += '?';
		}
	}
	cout<<wy<<"\n";
	return 0;
}