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

#define pb push_back
#define fi first
#define sn second

typedef long long ll;
typedef vector<int> VI;
typedef vector<char> VC;
typedef pair<int, int> PI;

struct FuStruct {
  int parent;
  int rank;
  int size;
  int computers;
  char status;
  bool done;
};

struct Query {
  char c;
  int x;
  int y;
};

const char has = '1';
const char nothas = '0';
const char dunno = '?';

vector<FuStruct> fus;

int fu_find(int x) {
  if (fus[x].parent != x) {
    fus[x].parent = fu_find(fus[x].parent);
  }
  return fus[x].parent;
}

void fu_union(int x, int y) {
  int x_set = fu_find(x);
  int y_set = fu_find(y);

  if (x_set == y_set) return;

  if (fus[x_set].rank < fus[y_set].rank) {
    fus[y_set].size += fus[x_set].size;
    fus[y_set].computers += fus[x_set].computers;
    fus[x_set].parent = y_set;
  } else if (fus[x_set].rank > fus[y_set].rank) {
    fus[x_set].size += fus[y_set].size;
    fus[x_set].computers += fus[y_set].computers;
    fus[y_set].parent = x_set;
  } else {
    fus[x_set].size += fus[y_set].size;
    fus[x_set].computers += fus[y_set].computers;
    fus[y_set].parent = x_set;
    fus[x_set].rank = fus[x_set].rank + 1;
  }
}

int main() {
  int n, q;
  cin >> n >> q;

  vector<Query> queries(q);

  int removals = 0;

  for (int i = 0; i < q; i++) {
    cin >> queries[i].c;

    if (queries[i].c == '?' || queries[i].c == '-') {
      cin >> queries[i].x;
      queries[i].x -= 1;
      if (queries[i].c == '-') {
        removals++;
      }
    } else {
      cin >> queries[i].x >> queries[i].y;
      queries[i].x -= 1;
      queries[i].y -= 1;
    }
  }

  VI identity(n);
  for (int i = 0; i < n; i++) identity[i] = i;

  int next_id = n;

  int m = n + removals + 1;
  fus.resize(m);

  for (int i = 0; i < m; i++) {
    fus[i].parent = i;
    fus[i].rank = 0;
    fus[i].size = 1;
    fus[i].computers = 0;
    fus[i].status = nothas;
    fus[i].done = false;
  }

  for (Query q : queries) {
    int target_x = identity[q.x];

    if (q.c == '?') {
      if (fus[target_x].done) {
        cout << fus[target_x].status;
      } else {
        int parent = fu_find(target_x);

        if (fus[parent].size == fus[parent].computers) {
          fus[target_x].status = has;
        } else if (fus[parent].computers == 0) {
          fus[target_x].status = nothas;
        } else {
          fus[target_x].status = dunno;
        }

        cout << fus[target_x].status;
      }
    } else if (q.c == '-') {
      fus[target_x].status = nothas;
      fus[target_x].done = true;

      int parent = fu_find(target_x);
      fus[parent].size -= 1;
      fus[parent].computers -= 1;

      identity[q.x] = next_id;
      next_id++;
    } else {
      int target_y = identity[q.y];

      fu_union(target_x, target_y);
      int parent = fu_find(target_x);
      fus[parent].computers += 1;
    }
  }
  cout << endl;

  return 0;
}