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
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define mid ((l+r)/2)
#define siz(x) (int)(x).size()
#define BOOST ios_base::sync_with_stdio(0), cin.tie(0)
#define deb(x) cout << #x << ": " << x << "\n"
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;

const int N = 1e6 + 5;
int Union[N];
vector<int> memb[N];
int active[N];
bool comp[N];

int cnt = 1;

void merge(int a, int b){
	if(siz(memb[Union[a]]) < siz(memb[Union[b]])) swap(a, b);

	if(Union[a] == 0 && Union[b] == 0){
		Union[a] = cnt;
		memb[cnt].pb(a);
		if(a != b){
			Union[b] = cnt;
			memb[cnt].pb(b);
			active[cnt] = 2;
		}
		else{
			active[cnt] = 1;
			comp[cnt] = 1;
		}
		cnt++;
		return;
	}

	if(Union[b] == 0){
		Union[b] = Union[a];
		memb[Union[a]].pb(b);
		active[Union[a]]++;
		return;
	}

	if(Union[a] != Union[b]){
		int old = Union[b];
		for(auto it : memb[old]){
			if(Union[it] == old){
				Union[it] = Union[a];
				memb[Union[a]].pb(it);
				active[Union[a]]++;
			}
		}
		vector<int>().swap(memb[old]);
		if(comp[old]) comp[Union[a]] = 1;
		return;
	}

	if(Union[a] == Union[b]){
		comp[Union[a]] = 1;
	}
}

int main(){
	BOOST;
	int n, q;
	cin >> n >> q;
	for(int i=0; i<q; i++){
		int a, b;
		char c;
		cin >> c >> a;
		if(c == '+'){
			cin >> b;
			merge(a, b);
		}
		if(c == '-'){
			int old = Union[a];
			Union[a] = 0;
			active[old]--;
			if(active[old] == 1 && comp[old] == 0){
				for(auto it : memb[old]){
					if(Union[it] == old) Union[it] = 0;
				}
				vector<int>().swap(memb[old]);
			}
		}
		if(c == '?'){
			if(Union[a] == 0) cout << 0;
			else if(comp[Union[a]]) cout << 1;
			else cout << '?';
		}
	}
}