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
// 2024 HOPE IN VALUABLE
#include<bits/stdc++.h>
using namespace std;
const int N=1300005;
int n,Q,ans[N],id[N],ff[N]; set<int>s[N];
inline int find(int x){ return ff[x]==x?x:ff[x]=find(ff[x]); }
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>Q;
	for(int i=1;i<=n;i++) ff[i]=id[i]=i,s[i].emplace(i);
	while(Q--){
		string opt; cin>>opt;
		if(opt=="?"){
			int x; cin>>x; x=find(id[x]);
			if(ans[x]==1) cout<<"1";
			else if(ans[x]==0) cout<<"0";
			else cout<<"?";
		}
		if(opt=="+"){
			int x,y; cin>>x>>y;
			x=find(id[x]); y=find(id[y]);
			if(x==y){ ans[x]=1; continue; }
			if(s[x].size()<s[y].size()) swap(x,y);
			ff[y]=x; for(int z:s[y]) s[x].emplace(z); s[y].clear();
			if(ans[x]==1||ans[y]==1) ans[x]=1;
			else ans[x]=-1;
		}
		if(opt=="-"){
			int x; cin>>x;
			if(ans[find(id[x])]==-1&&s[find(id[x])].size()==2) ans[find(id[x])]=0;
			s[find(id[x])].erase(x);
			id[x]=++n; ff[n]=n; s[n].emplace(x);
		}
	}
	return 0;
}