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
#include<bits/stdc++.h>
using namespace std;
int dset[300005];
int Size[300005];
int stan[300005];
int n;
int find(int a)
{
    if(dset[a]!=a) dset[a]=find(dset[a]);
    return dset[a];
}
void unite(int a, int b)
{
    if(Size[a] > Size[b]){
        dset[b] = a;
        Size[a]+=Size[b];
        Size[b]=1;
    }
    else{
        dset[a] = b;
        Size[b]+=Size[a];
        Size[a]=1;
    }
}
void del(int a)
{
    if(find(a)!=a){
        for(int i=0; i<n+2; i++){
            if(dset[i]==a) find(i);
        }
        Size[find(a)]--;
        if(Size[find(a)]==1&&stan[find(a)]==1){
            stan[find(a)]=0;
        }
        dset[a]=a;
        stan[a]=0;
        find(a);
        return;
    }
    else{
        int p=-1;
        for(int i=0; i<n+2; i++){
            if(find(i)==a&&i!=a){
                p=i;
                break;
            } 
        }
        if(p==-1){
            stan[a]=0;
            Size[a]=1;
            return;
        }
        for(int i=0; i<n+2; i++){
            if(find(i)==a&&i!=a) dset[i]=p;
        }
        Size[p]=Size[a]-1;
        stan[p]=stan[a];
        if(stan[p]==1&&Size[p]==1) stan[p]=0;
        Size[a]=1;
        stan[a]=0;
        return;
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int q;
    cin>>n>>q;
    for(int i=0; i<n+2; ++i){
        dset[i]=i;
        Size[i]=1;
    }
    for(int i=0; i<q; i++){
        char c;
        cin>>c;
        if(c=='?'){
            int a;
            cin>>a;
            if(stan[find(a)]==0) cout<<'0';
            if(stan[find(a)]==1) cout<<'?';
            if(stan[find(a)]==2) cout<<'1';
        }
        if(c=='+'){
            int a, b;
            cin>>a>>b;
            if(a==b){
                stan[find(a)]=2;
                continue;
            }
            if(find(a)==find(b)){
                stan[find(a)]=2;
            }
            else{
                int pom=1;
                if(stan[find(a)]==2||stan[find(b)]==2) pom=2;
                unite(find(a), find(b));
                stan[find(a)]=pom;
            }
        }
        if(c=='-'){
            int a;
            cin>>a;
            del(a);
        }
    }
    return 0;
}