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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
using namespace std;
array <int,1000001> r;
array <int,1000001> p,d;
array <int,1000001> g;
array <int,1000001> f;
array <int,1000001> s;
vector<int>u,v;
int i,j,q,n,a,b,m,x,h;
char c;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	x=0;
	for(i=0;i<q;i++) {
		//for(j=0;j<=n;j++)
		//	cout << r[j] << 'g' << g[j] << ' ';
		//cout << i << '\n';
		cin >> c;
		if(c=='+') {
			cin >> a >> b;
			//cout << a<<b <<'\n';
			if(a==b && r[a]==-1) 
				r[a]=1;
			else if (a==b && r[a]==0) {
				r[a]=1;
				continue;
			}
			if(r[b]>r[a]) {
				m=b;
				b=a;
				a=m;
			}
			if(r[a]==1 && r[b]==0) 
				r[b]=1;
			else if(r[a]==1 || (r[a]==-1 && r[b]==-1 && g[a]==g[b])) {
				h=f[g[b]];
				while(h>0) {
					g[h]=0;
					r[h]=1;
					h=p[h];
				}
				
			}
			else if(r[a]==0 && r[b]==-1){
				p[a]=f[g[b]];
				d[f[g[b]]]=a;
				d[a]=0;
				g[a]=g[b];
				f[g[b]]=a;
				s[g[b]]++;
				r[a]=-1;
			}
			else if(r[a]==0 && r[b]==0){
				x++;
				s[x]=2;
				p[b]=0;
				p[a]=b;
				d[b]=a;
				d[a]=0;
				f[x]=a;
				g[a]=x;
				g[b]=x;
				r[a]=-1;
				r[b]=-1;
				
			}
			else {
				if(s[g[a]]<s[g[b]]){ 
					m=a;
					a=b;
					b=m;
				}
				s[g[a]]+=s[g[b]];
				h=f[g[b]];
				j=f[g[a]];
				f[g[a]]=h;
				m=g[a];
				while(p[h]>0){
					g[h]=m;
					h=p[h];
				}
				g[h]=g[a];
				p[h]=j;
				d[j]=h;
			}

		}

		else if(c=='-'){
			cin >> a;
			//cout << a << '\n';
			if(r[a]==1) r[a]=0;
			else{
				r[a]=0;
				s[g[a]]--;
				if(d[a]==0) {
					f[g[a]]=p[a];
					d[p[a]]=0;
					
				}
				else{
					p[d[a]]=p[a];
					if(p[a]>0)
						d[p[a]]=d[a];
				}
				if(s[g[a]]==1) {
					r[f[g[a]]]=0;

				}
			}
		}
		else {
			cin >> a;
			//cout << "X" << a << '\n';
			if(r[a]>=0)
				cout << r[a];
			else
				cout << '?';
		}
	}
}