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
107
108
109
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int M = 1001013;
const int U = 2001013;
const int N = 301013;

#define DBG 0

vector<int> v[U];
int u[U], gd[U], byl[U], si[U];
int st[N];

void dfs(int x, int co) {
	if (st[byl[x]] == x) {
		st[byl[x]] = co;
	}
	for (int i : v[x]) {
		if(i != x) dfs(i, co);
	}
}

void od(int a) {
	vector<int>& vu = v[u[a]];
	gd[vu.back()] = gd[a];
	vu[gd[a]] = vu.back();
	vu.pop_back();
}

void dop(int a, int b) {
	if (DBG) printf(" $$$ dopinam %d do %d\n", a,b);
	u[a] = b;
	gd[a] = v[b].size();
	v[b].push_back(a);
}

int uw(int x) {
	if (u[x] == x) return x;
	int nu = uw(u[x]);
	od(x);
	dop(x, nu);
	return nu;
}

void lacz(int a, int b) {
	if (DBG) printf("     lacze %d %d\n", a,b);
	if (uw(a) == uw(b)) {
		dfs(u[a], -1);
		return;
	}
	if(DBG) printf("  faktycznie lacze\n");
	si[u[a]] += si[u[b]];
	si[u[b]] = 0;
	od(u[b]);
	dop(u[b], u[a]);
}

void odlacz(int a) {
	if (--si[uw(a)] == 1) { 
		dfs(u[a], 0);
	}
}

void nowy(int a, int kim) {
	byl[a] = kim;
	si[a] = 1;
	if (DBG) printf(" __ podpinam nowy %d do %d\n", a, a);
	dop(a, a);
}

char pyt(int a) {
	if (DBG) printf("  pytam %d - odp %d\n",a,st[a]);
	if (st[a] > 0) return '?';
	if (st[a] == 0) return '0';
	return '1';
}

char ret[M];

int main() {
	int n, q, a, b, new_id = 1, rr = 0;
	scanf("%d %d", &n, &q);
	char ss[13];
	for (int i = 0; i < q; i++) {
		if(DBG) printf("polecenie %d ::\n", i);
		scanf("%s %d", ss, &a);
		if (ss[0] == '+') {
			scanf("%d", &b);
			if (st[a] == -1) a = b;
			if (st[b] == -1) b = a;
			if (a == b && st[a] == 0) {
				st[a] = -1;
			} else {
				if (st[a] == 0) nowy(st[a] = new_id++, a);
				if (st[b] == 0) nowy(st[b] = new_id++, b);
				lacz(st[a], st[b]);
			}
		} else if (ss[0] == '-') {
			if (st[a] > 0) odlacz(st[a]);
			st[a] = 0;
		} else {
			ret[rr++] = pyt(a);
		}
	}
	puts(ret);
	return 0;
}