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
105
106
#include <bits/stdc++.h>

using namespace std;

const int N = 300'000 + 7;
const int Q = 1'000'000 + 7;

int n, q;

int cur[N];
int val[N + Q];

int uf[N + Q], sz[N + Q], cycle[N + Q];

int get(int u) {
	return u == uf[u] ? u : uf[u] = get(uf[u]);
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);

	for (int i = 0; i < N + Q; i++) {
		uf[i] = i;
		sz[i] = 1;
		cycle[i] = 0;
	}

	cin >> n >> q;
	
	for (int i = 1; i <= n; i++) {
		val[i] = -1;
		cur[i] = i;
	}

	int nxt = n + 1;
	
	for (int rep = 0; rep < q; rep++) {
		char op;
		cin >> op;

		if (op == '+') {
			int a, b;
			cin >> a >> b;

			a = cur[a];
			b = cur[b];

			val[a] = 0;
			val[b] = 0;

			a = get(a);
			b = get(b);

			if (a == b) {
				cycle[a] = +1;
			}
			else {
				uf[b] = a;
				sz[a] += sz[b];

				if (cycle[a] == +1 || cycle[b] == +1) {
					cycle[a] = +1;
				}
			}
		}
		else
		if (op == '-') {
			int c;
			cin >> c;
			
			int old = c;

			c = cur[c];
			sz[get(c)]--;
			val[c] = +1;

			c = old;

			cur[c] = nxt++;
			c = cur[c];
			val[c] = -1;
		}
		else
		if (op == '?') {
			int d;
			cin >> d;

			d = cur[d];

			if (cycle[get(d)] == +1 || val[d] == +1)
				cout << '1';
			else
			if (val[d] == -1 || sz[get(d)] == 1)
				cout << '0';
			else
				cout << '?';
		}
		else {
			assert(false);
		}
	}
	
	cout << '\n';

	return 0;
}