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
#include<iostream>
#include<unordered_map>

#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)

using namespace std;

const int MAXN = 300000;

int T[1+MAXN], F[1+MAXN], L[1+MAXN], R[1+MAXN];
int n, q, a, b, c, d, m;
char ch;

unordered_map<int,int> S;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> q;
	FOR(i, 1, n) { T[i]=i; F[i]=0; L[i]=i; R[i]=i; S[i]=i; } 
	m = n;
	REP(i, q) {
		// if (i % 10000 == 0) cerr << "i=" << i << endl;
		cin >> ch;
		if (ch == '+') {
			cin >> a >> b;
			if (T[a] != T[b]) { 
				if (S[T[a]] > S[T[b]]) { c=a;a=b;b=c; }
				
				int F_ab = (F[a] == 1 || F[b] == 1) ? 1 : -1;
				int T_a = T[a], T_b = T[b];

				{ int j = a; do { T[j] = T_b; j = L[j]; } while (j!=a); }
				
				if (F[a] != F_ab) { int j = a; do { F[j] = F_ab; j = L[j]; } while (j!=a); }
				if (F[b] != F_ab) { int j = b; do { F[j] = F_ab; j = L[j]; } while (j!=b); }

				int R_a = R[a]; R[a] = b;
				int L_b = L[b]; L[b] = a;
				L[R_a] = L_b; R[L_b] = R_a;
				
				S[T_b] += S[T_a];
				
			} else if (F[a] != 1) { 
				// fossilize the tree once
				int j = a; do { F[j]=1 ; j=L[j]; } while (j!=a);
			}
		} else if (ch == '-') {
			cin >> c;
			int vtx = 0;			
			int j = c; if (F[c] == -1) do { vtx++; d=j ; j = L[j]; } while (j!=c && vtx <= 2);

			F[c] = 0;
			T[c] = ++m;
			S[m] = 1;
			int L_c = L[c], R_c = R[c]; R[L_c] = R_c; L[R_c] = L_c; L[c] = R[c] = c;
			
			if (vtx == 2) {
				F[d] = 0;
				T[d] = ++m;
				S[m] = 1;
				int L_d = L[d], R_d = R[d]; R[L_d] = R_d; L[R_d] = L_d; L[d] = R[d] = d;
			}
			
		} else if (ch == '?') {
			cin >> d;
			if (F[d] >= 0) {
				cout << F[d];
			} else {
				cout << '?';
			}
		}
	}	
	cout << endl;
	return 0;
}