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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <bits/stdc++.h>
#define pb emplace_back
#define FOR(i,a,b) for(int i = a; i < b;++i)
using namespace std;
const int maxn = 1300 * 1000 + 25,maxn1 = 1300 * 1000 + 5;
vector<int> par,vis(maxn,0),stan(maxn,0),kto(maxn,0),ans,to(maxn,0);
set<int> V[maxn];
int cnt = 0,lic = 1;
inline int f(int v){ ///algorytm find and union
    if(v == par[v]){
        return v;
    }
    return par[v] = f(par[v]);
}
inline void u(int a,int b){
    a = f(a);
    b = f(b);
    if(a != b){
        par[a] = b;
    }
}
inline void dfs(int v){ ///algorytm dfs
    v = to[v];
    for(auto y : V[v]){
        y = to[y];
        if(vis[y] != lic){
            vis[y] = lic;
            if(stan[y] == 2){
                stan[y] = 1;
            }
            dfs(y);
        }
    }
    V[v].clear();
    par[v] = v;
}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n,q;
    cin>>n >>q;
    FOR(i,0,maxn){
        par.pb(i);
        to[i] = i;
    }
    FOR(i,0,maxn1){
        kto[i] = i;
    }
    cnt = maxn1;

    FOR(i,0,q){
        char x;
        cin>>x;
        if(x == '?'){
            int y;
            cin>>y;
            ans.pb(stan[kto[y]]);
        }
        if(x == '+'){
            int a,b;
            cin>>a >>b;
            if(a == b){
                stan[kto[a]] = 1;
                dfs(kto[a]);
                ++lic;
                continue ;
            }
            if(stan[kto[a]] + stan[kto[b]] == 1){
                stan[kto[b]] = 1;
                stan[kto[a]] = 1;
                continue;
            }
            if(stan[kto[a]] == 0 && stan[kto[b]] == 0){
                u(kto[a],kto[b]);
                stan[kto[a]] = 2;
                stan[kto[b]] = 2;
                V[kto[a]].insert(kto[b]);
                V[kto[b]].insert(kto[a]);
                continue;
            }
            if(stan[kto[a]] == 2 && stan[kto[b]] == 2 && f(kto[a]) == f(kto[b])){
                dfs(kto[a]);
                ++lic;
                continue;
            }
            if(stan[kto[a]] == 2 && stan[kto[b]] == 2 && f(kto[a]) != f(kto[b])){
                V[kto[a]].insert(kto[b]);
                V[kto[b]].insert(kto[a]);
                u(kto[a],kto[b]);
                continue;
            }
            if(stan[kto[a]] == 1 && stan[kto[b]] == 2){
                V[kto[a]].insert(kto[b]);
                V[kto[b]].insert(kto[a]);
                u(kto[a],kto[b]);
                dfs(kto[a]);
                ++lic;
                continue;
            }
            if(stan[kto[a]] == 2 && stan[kto[b]] == 1){
                V[kto[a]].insert(kto[b]);
                V[kto[b]].insert(kto[a]);
                u(kto[a],kto[b]);
                dfs(kto[b]);
                ++lic;
                continue;
            }
            if((stan[kto[a]] == 0 && stan[kto[b]] == 2 )|| (stan[kto[a]] == 2 && stan[kto[b]] == 0)){
                V[kto[a]].insert(kto[b]);
                V[kto[b]].insert(kto[a]);
                u(kto[a],kto[b]);
                stan[kto[a]] = 2;
                stan[kto[b]] = 2;
                continue;
            }
        }
        if(x == '-'){
            int v;
            cin>>v;
            int v1 = kto[v];
            stan[v1] = 0;
            if(V[v1].size() != 0){
                int p1 = to[*V[v1].begin()];
                if(V[v1].size() == 1 && V[to[p1]].size() == 1){
                    stan[to[p1]] = 0;
                }
                to[v1] = p1;
                for(auto &y : V[v1]){
                    if(to[y] != p1){
                        V[p1].insert(to[y]);
                    }
                }
                V[v1].clear();
                kto[v] = cnt;
                ++cnt;
            }
         }

    }
    for(auto &y : ans){
        if(y == 2){
            cout<<"?";
        }else{
            cout<<y;
        }
    }
}