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<iostream> 
#include<algorithm>
#include<vector>
using namespace std;

vector<int> ch[300001];
bool j[300001];

struct FAU {
	int *p,*w;
	FAU(int n) : p(new int[n]), w(new int[n]) {
		for(int x=0; x<n; ++x) p[x] = w[x] = -1;
	}
	~FAU() {
		delete[]p;
		delete[]w;
	}
	int Find(int x) {
		return (p[x] < 0) ? x : Find(p[x]);
	}
	void Union(int x, int y) {
		if((x = Find(x)) == (y = Find(y))) return;
		if(j[x] || j[y]) j[x] = j[y] = true;
		if(w[x] > w[y]) {
			p[y] = x;
			ch[x].push_back(y);
		}
		else {
			p[x] = y;
			ch[y].push_back(x);
		}
		if(w[x] == w[y]) w[y]++;
	}
	void deletion(int x) {
		if(p[x] != -1)
		for(int i=0; i<ch[p[x]].size(); ++i) {
			if(ch[p[x]][i] == x) ch[p[x]].erase(ch[p[x]].begin()+i);
		}
		int nr,l;
		l = ch[x].size();
		if(l == 0) {
			p[x] = w[x] = -1;
			j[x] = false;
			return;
		}
		nr = ch[x][(l-1)/3];
		p[nr] = p[x];
		w[nr] = w[x];
		j[nr] = j[x];
		for(int i=0; i<l; ++i) {
			if(i != (l-1)/3) {
				ch[nr].push_back(ch[x][i]);
				p[ch[x][i]] = nr;
			}
		}
		if(p[x] != -1) ch[p[x]].push_back(nr);
		ch[x].clear();
		p[x] = w[x] = -1;
		j[x] = false;
	}
};

int main() {
	ios::sync_with_stdio(0);
	int N,Q;
	cin>>N>>Q;
	j[N] = true;
	for(int i=0; i<N; ++i) j[i] = false;
	FAU fau(N+1);
	char A;
	for(int i=0; i<Q; ++i) {
		cin>>A;
		if(A == '+') {
			int a,b;
			cin>>a>>b;
			a--;
			b--;
			a = fau.Find(a);
			b = fau.Find(b);
			if(a == b) {
				fau.Union(a,N);
			}
			else {
				fau.Union(a,b);
			}
		}
		if(A == '-') {
			int c;
			cin>>c;
			c--;
			fau.deletion(c);
		}
		if(A == '?') {
			int d;
			cin>>d;
			d--;
			d = fau.Find(d);
			if(j[d]) cout<<"1";
			else if(ch[d].size() == 0) cout<<"0";
			else cout<<"?";
		}
	}
	cout<<endl;
	
	return 0;
}