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
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for(int i=a; i>=b; --i)
#define ssize(v) (int)(v.size())
#define eb push_back

constexpr int MAX_N=3e5+14, MAX_Q=1e6+14;

int N, qtQ;
char rres[MAX_N];
int fau[MAX_N];
vector<int> vecFrom[MAX_N];
void Input(){
    cin>>N>>qtQ;
    FOR(i,1,N){
        rres[i]='0';
        fau[i]=i;
        vecFrom[i]={i};
    }
}
int Find(int v){
    if(fau[v]==v)
        return v;
    fau[v]=Find(fau[v]);
    return fau[v];
}
void Union(int a, int b){
    vecFrom[Find(a)].insert(vecFrom[Find(a)].end(),
        vecFrom[Find(b)].begin(), vecFrom[Find(b)].end());
    vecFrom[Find(b)].clear();
    vecFrom[Find(a)].shrink_to_fit(), vecFrom[Find(b)].shrink_to_fit();
    fau[Find(b)] = Find(a);
}
void Add(int a){
    for(auto nE:vecFrom[a]){
        if(nE==a) continue;
        rres[nE]='1';
        fau[nE]=nE;
        vecFrom[nE]={nE};
    }
    rres[a]='1';
    fau[a]=a;
    vecFrom[a]={a};
}
void Minus(int a){
    if(ssize(vecFrom[Find(a)])==1) return;
    int firD=0;
    for(auto cE:vecFrom[Find(a)])
        if(cE!=a) {firD=cE; break;}

    if(ssize(vecFrom[Find(a)])==2){
        fau[firD]=firD;
        vecFrom[firD]={firD};
        rres[firD]='0';
        fau[a]=a;
        vecFrom[a]={a};
        return;
    }
    if(Find(a)==a){
        vecFrom[firD].clear();
        FOR(i,0,ssize(vecFrom[a])-1){
            if(vecFrom[a][i]==a) continue;
            vecFrom[firD].eb(vecFrom[a][i]);
            fau[vecFrom[a][i]]=firD;
        }
        fau[a]=a, vecFrom[a]={a};
    }else{
        FOR(i,0,ssize(vecFrom[fau[a]])-1) if(vecFrom[fau[a]][i]==a){vecFrom[fau[a]].erase(vecFrom[fau[a]].begin()+i); break;};
        FOR(i,0,ssize(vecFrom[fau[a]])-1) fau[vecFrom[fau[a]][i]]=fau[a];
        fau[a]=a, vecFrom[a]={a};
        vecFrom[fau[a]].shrink_to_fit();
        vecFrom[a].shrink_to_fit();

        return;
    }
}
void Solve(){
    char a;
    int b, c;

    FOR(qq,1,qtQ){
        cin>>a;
        if(a=='?') cin>>b, cout<<rres[b];
        else if(a=='+'){
            cin>>b>>c;
            if(rres[b]=='1'&&rres[c]=='1') {}
            else if(rres[b]=='1') Add(Find(c));
            else if(rres[c]=='1') Add(Find(b));
            else if(Find(b)==Find(c)){
                Add(Find(b));
            }else{
                Union(b,c);
                rres[b]='?', rres[c]='?';
            }
        }else{
            cin>>b;
            if(rres[b]=='?') Minus(b);
            rres[b]='0';
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    Input();
    Solve();
}