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
 98
 99
100
101
102
103
104
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r)for(int i=(l);i<=(r);++i)
#define REP(i,n)FOR(i,0,(n)-1)
#define ssize(x)int(x.size())
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto&operator<<(auto&o,tuple<auto,auto,auto>t){return o<<"("<<get<0>(t)<<", "<<get<1>(t)<<", "<<get<2>(t)<<")";}
auto&operator<<(auto&o,tuple<auto,auto,auto,auto>t){return o<<"("<<get<0>(t)<<", "<<get<1>(t)<<", "<<get<2>(t)<<", "<<get<3>(t)<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct FindUnion {
	vector<int> rep, marked, edges;
	int size(int x) { return -rep[find(x)]; }
	int find(int x) {
		return rep[x] < 0 ? x : rep[x] = find(rep[x]);
	}
	bool same_set(int a, int b) { return find(a) == find(b); }
	void add_edge(int a, int b) {
		a = find(a), b = find(b);
		if(a == b) {
			++edges[a];
			return;
		}
		if(-rep[a] < -rep[b])
			swap(a, b);
		++edges[a];
		rep[a] += rep[b];
		rep[b] = a;
		edges[a] += edges[b];
		marked[a] += marked[b];
		return;
	}
	void mark_vertex(int a) {
		++marked[find(a)];
	}
	int get_edges(int a) {
		return edges[find(a)];
	}
	int get_marked(int a) {
		return marked[find(a)];
	}
	FindUnion(int n) : rep(n, -1), marked(n, 0), edges(n, 0) {}
};

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int n, q;
	cin >> n >> q;

	int next_vertex = 0;
	auto new_vertex = [&]() {
		return next_vertex++;
	};

	vector<int> vertex(n);
	REP(i, n) {
		vertex[i] = new_vertex();
	}
	FindUnion fu(n + q);

	REP(i, q) {
		char type; 
		cin >> type;
		if (type == '+') {
			int x, y;
			cin >> x >> y;
			--x, --y;
			fu.add_edge(vertex[x], vertex[y]);
		}
		else if (type == '-') {
			int x;
			cin >> x;
			--x;
			fu.mark_vertex(vertex[x]);
			vertex[x] = new_vertex();
		}
		else if (type == '?') {
			int x;
			cin >> x;
			--x;
			x = vertex[x];
			const int edges = fu.get_edges(x);
			const int marked = fu.get_marked(x);
			const int size = fu.size(x);
			if (edges == size)
				cout << '1';
			else if (marked == size - 1)
				cout << '0';
			else
				cout << '?';
		}
		else {
			assert(false);
		}
	}
	cout << '\n';
}