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
#include <bits/stdc++.h>

using namespace std;

int P[(int)2e6];
int R[(int)2e6];
bool K[(int)2e6];
int re[(int)2e6];
int L[(int)2e6];

int find(int x){
  if(P[x]!=x){
    P[x] = find(P[x]);
  }
  return P[x];
}

void Union(int x, int y){
  int px=find(x);
  int py=find(y);
  if(R[px]<R[py]){
    P[px]=py;
    L[py]+=L[px];
    if(K[px])K[py]=true;
  }
  else if(R[px]>R[py]){
    P[py]=px;
    L[px]+=L[py];
    if(K[py])K[px]=true;
  }
  else{
    P[py]=px;
    R[px]++;
    L[px]+=L[py];
    if(K[py])K[px]=true;
  }
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie();
cout.tie();
  int n,q;cin>>n>>q;
  for(int i=1;i<=n;i++){
    P[i]=i;re[i]=i;R[i]=1;K[i]=false;L[i]=1;
  }
  while(q--){
    char x;cin>>x;
    if(x=='+'){
      int a,b;cin>>a>>b;
      a=re[a];b=re[b];
      if(find(a)!=find(b))Union(a,b);
      else K[find(a)]=true;
    }
    if(x=='-'){
      int c;cin>>c;
      n++;
      L[find(re[c])]--;
      re[c]=n;P[re[c]]=re[c];K[re[c]]=false;
      L[re[c]]=1;
    }
    if(x=='?'){
      int d;cin>>d;
      d=re[d];
      if(K[find(d)])cout<<1;
      else if(L[find(d)]==1)cout<<0;
      else cout<<"?";
    }
  }
  cout<<"\n";
return 0;
}