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

namespace std {

template<class Fun>
class y_combinator_result {
	Fun fun_;
public:
	template<class T>
	explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

	template<class ...Args>
	decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

} // namespace std

int main(){
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int N, Q;
	cin >> N >> Q;
	vector<int> label(N);
	for(int i = 0; i < N; i++) label[i] = i;
	vector<int> par(N);
	vector<int> alive_verts(N);
	vector<int> alive_edges(N);
	for(int i = 0; i < N; i++){
		par[i] = i;
		alive_verts[i] = 1;
		alive_edges[i] = 0;
	}
	auto find = y_combinator(
		[&](auto self, int v) -> int {
			if(par[v] != v) par[v] = self(par[v]);
			return par[v];
		}
	);
	string answers;
	while(Q--){
		char type;
		cin >> type;
		if(type == '-'){
			int c;
			cin >> c;
			c--;
			int v_prv = find(label[c]);
			alive_verts[v_prv]--;
			alive_edges[v_prv]--;
			assert(alive_verts[v_prv] >= alive_edges[v_prv]);

			int v_cur = (int)par.size();
			label[c] = v_cur;
			par.resize(v_cur+1); alive_verts.resize(v_cur+1); alive_edges.resize(v_cur+1);
			par[v_cur] = v_cur;
			alive_verts[v_cur] = 1;
			alive_edges[v_cur] = 0;
		} else if(type == '+'){
			int a, b;
			cin >> a >> b;
			a--; b--;
			int v1 = find(label[a]);
			int v2 = find(label[b]);
			if(v1 == v2){
				alive_edges[v1]++;
			} else {
				par[v2] = v1;
				alive_verts[v1] += alive_verts[v2];
				alive_edges[v1] += alive_edges[v2];
				alive_edges[v1]++;
				alive_verts[v2] = alive_edges[v2] = 0;
			}
		} else if(type == '?'){
			int d;
			cin >> d;
			d--;
			int v = find(label[d]);
			if(alive_verts[v] == alive_edges[v]){
				answers += "1";
			} else if(alive_edges[v] == 0){
				answers += "0";
			} else {
				answers += "?";
			}
		}
	}
	cout << answers << '\n';
}