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
# include <bits/stdc++.h>
# define For(i, l, r) for(int i = (l); i <= (r); i++)
# define Rep(i, n) For(i, 0, (n) - 1)
# define size(x) (ll)x.size()
# define MAXSZ 300005
# define all(x) x.begin(),x.end()
using namespace std;
typedef int ll;
typedef long double ld;
const ll inf = 1e9 + 7;
const ll mod = 1e9 + 7;
ll n , m , k , q , t;
vector<ll> col(MAXSZ) , root(MAXSZ) , Rank(MAXSZ);
vector<vector<ll> >g(MAXSZ);
void init() {
      For (i , 1 , n) {
            root[i] = i;
            Rank[i] = 1;
            col[i] = 0;
      }
}
ll get_r(ll x , ll odj) {
    Rank[x] -= odj;
    if (root[x] == x) return x;
    else return get_r(root[x] , odj);
}
void clear(ll v) {
     ll r = get_r(v , 0);
     queue<ll>q;
     q.push(r);
     while (!q.empty()) {
        ll v = q.front();
        q.pop();
        root[v] = v;
        Rank[v] = 1;
        col[v] = 1;
        for (auto to : g[v]) {
             q.push(to);
        }
        g[v].clear();
     }           
}
pair<ll , ll> Union(ll r1 , ll r2) {
       if (Rank[r1] < Rank[r2]) swap(r1 , r2);
       root[r2] = r1;
       g[r1].push_back(r2);
       return {r1 , r2};
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    init();
    while (q--) {
      char c;
      cin >> c;
      if (c == '+') {
         ll ai , bi;
         cin >> ai >> bi;
         if (col[ai] || col[bi]) {
              if (col[ai]) swap(ai , bi);
              clear(ai);
              continue;
         }
         ll r1 = get_r(ai , 0) , r2 = get_r(bi , 0);
         if (r1 == r2 || ai == bi) { 
               clear(r1);
         } else {
               auto [rr1 , rr2] = Union(r1 , r2);
               Rank[rr1] += Rank[rr2];
         }
      } else if (c == '-') {
         ll ci;
         cin >> ci;
         ll rci = get_r(ci , 1);
         col[ci] = 0;
         ll up = (root[ci] == ci ? -1 : root[ci]);
         ll down = -1;
         if (size(g[ci]) > 0) {
               down = g[ci][0];
               For (i , 1 , size(g[ci]) - 1) {
                  auto [new_down , prev] = Union(down , g[ci][i]);
                  down = new_down;
                  Rank[new_down] += Rank[prev];
               }
               g[ci].clear();
         }
         root[ci] = ci;
         Rank[ci] = 1;
         if (up != -1) {
            Rep (i , size(g[up])) if (g[up][i] == ci) {
                  swap(g[up][i] , g[up].back());
                  g[up].pop_back();
                  break;
            }
         }
         if (up != -1 && down != -1) {  
            root[down] = up;
            g[up].push_back(down);
         } else if (down != -1) {
            root[down] = down;
         }
      } else {
         ll di;
         cin >> di;
         if (root[di] == di && Rank[di] == 1) cout << col[di];
         else cout << '?';
      }
    }
}
//odjgoadfhfoav hash1 i hash2 (hash1 * 1e9 + hash