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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+7;	
int w[MAXN],ans[MAXN],rep[MAXN];
multiset<int>spojna[MAXN];
void Union(int ra,int rb){
	if(spojna[ra].size()>spojna[rb].size()) swap(ra,rb);
	ans[rb]=max(ans[rb],ans[ra]);
	for(auto x:spojna[ra]){ spojna[rb].insert(x); rep[x]=rb; } 
	spojna[ra].clear();
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n,m,lw,a,a1,b,ra,rb; char c;
	cin>>n>>m;
	for(int i=1;i<MAXN;i++){
		rep[i]=w[i]=i;
		spojna[i].insert(i);
	} 
	for(int i=1;i<=m;i++){
		cin>>c;
		if(c=='?'){
			cin>>a; a=w[a]; ra=rep[a];
			if(ans[ra]==2) cout<<1; else if(ans[ra]==1) cout<<'?'; else cout<<0;
		}
		else if(c=='+'){
			cin>>a>>b;
			a=w[a]; b=w[b];
			ra=rep[a]; rb=rep[b];
			ans[ra]=max(ans[ra],1); ans[rb]=max(ans[rb],1);
			if(ra==rb) ans[ra]=2; else Union(ra,rb);
		}
		else{
			cin>>a; a1=a; 
			a=w[a]; ra=rep[a];
			spojna[ra].erase(a);
			if(spojna[ra].size()==1 and ans[ra]<2) ans[ra]=0;
			else if(ans[ra]<2) ans[ra]=1;
			w[a1]=++n;
		}
	}
	cout<<'\n';
	return 0;
}