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

using namespace std;

const int N = 2e6 + 5;
int n = 0, m = 0, q = 0, id[N] = {}, fa[N] = {}, siz[N] = {}, val[N] = {}, tag[N] = {};

inline int find(int x){
	if(fa[x] != x) fa[x] = find(fa[x]);
	return fa[x];
}

inline void merge(int x, int y){
	x = find(x), y = find(y);
	if(x == y) tag[x] = 1;
	else{
		if(siz[x] < siz[y]) swap(x, y);
		fa[y] = x, siz[x] += siz[y], val[x] += val[y], tag[x] |= tag[y];
	}
}

int main(){
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	for(int i = 0 ; i < N ; i ++) fa[i] = i, val[i] = siz[i] = 1, tag[i] = 0;
	cin >> n >> q;
	for(int i = 1 ; i <= n ; i ++) id[i] = ++ m;
	for(int i = 1, u = 0, v = 0 ; i <= q ; i ++){
		char p = ' ';
		cin >> p;
		if(p == '+'){
			cin >> u >> v;
			merge(id[u], id[v]);
		}
		else if(p == '-'){
			cin >> v;
			val[find(id[v])] --, id[v] = ++ m;
		}
		else if(p == '?'){
			cin >> v;
			v = find(id[v]);
			if(tag[v]) cout << '1';
			else if(val[v] > 1) cout << '?';
			else cout << '0';
		}
	}
	return 0;
}