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
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define fi first
#define se second
#define pn printf("\n")
#define ssize(x) int(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define bitcount(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
#define vv vector
void read(int &a){
		char c = getchar_unlocked(); a = 0;
		while(c<'0' || '9'<c) c = getchar_unlocked();
		while('0'<=c&&c<='9') a = (a<<3)+(a<<1)+c-'0', c = getchar_unlocked();
}
int inf = 2e09; ll infll = 2e18; int mod = (1<<23)*119+1;
struct dsu{
		vv<int> rep, sz, type, curr;
		vv<vv<int>> g;
		int n;
		void init(int N){
				n = N;
				rep.resize(n+1, 0), sz.resize(n+1, 1), type.resize(n+1, 0), g.resize(n+1), curr.resize(n+1, 0);
				for(int i = 1; i <= n; ++i) rep[i] = i, curr[i] = i;
		}
		int Find(int x){
				if(x != rep[x]) rep[x] = Find(rep[x]);
				return rep[x];
		}
		void dfs(int x, int par, bool zero){
				//~ printf("%d %d\n", x, par);
				//~ usleep(100000);
				for(int u : g[x]) if(u != par) dfs(u, x, zero);
				g[x] = vv<int>();
				rep[x] = x, sz[x] = 1, type[x] = zero ? 0 : 2;
		}
		void Union(int a, int b){
				a = curr[a], b = curr[b];
				if(type[a] > type[b]) swap(a, b);
				int A = Find(a), B = Find(b);
				//~ printf("%d %d: %d %d\n", a, b, A, B);
				if(A == B) dfs(a, 0, 0);
				else{
						if(type[b] == 2){ dfs(a, 0, 0); return; }
						g[a].emplace_back(b), g[b].emplace_back(a);
						if(sz[A] < sz[B]) swap(A, B);
						rep[B] = A, sz[A] += sz[B];
						type[a] = 1, type[b] = 1;
				}
		}
		void Remove(int x){
				int a = x;
				x = curr[x];
				int k = ssize(rep), X = Find(x);
				curr[a] = ssize(g);
				rep.emplace_back(k), sz.emplace_back(1), g.emplace_back(vv<int>()), type.emplace_back(0);
				--sz[X];
				if(sz[X] == 1) dfs(x, 0, 1);	
		}
};
void answer(){
		int n, q; scanf("%d%d\n", &n, &q);
		dsu dsu; dsu.init(n);
		string s = "";
		for(++q; --q; ){
				char c; int a, b; scanf("%c", &c);
				if(c == '+') read(a), read(b), dsu.Union(a, b)/*, printf("+ %d %d\n", a, b)*/;
				else if(c == '-') read(a), dsu.Remove(a)/*, printf("- %d\n", a)*/;
				else read(a), s += (dsu.type[dsu.curr[a]] == 1 ? "?" : (!dsu.type[dsu.curr[a]] ? "0" : "1"))/*, printf("? %d\n", a)*/;
				//~ for(int i = 1; i <= n; ++i) printf("%d ", dsu.type[dsu.curr[i]]);
				//~ pn;
		}
		for(char &u : s) putchar_unlocked(u);
		pn;
}
signed main(){
		int T = 1;
		//~ scanf("%d", &T);
		//~ ios_base::sync_with_stdio(0); cin.tie(0); //cin >> T;
		for(++T; --T; ) answer();
		return 0;
}