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
148
149
150
151
152
153
154
155
156
157
#include <cassert>
#include <cctype>
#include <cstdio>
#include <cstdlib>

#include <vector>

enum has_computer : char { no, maybe, yes };

struct union_find {
private:
  struct entry {
    int parent;
    int rank;
    int user_count;
    int comp_count;

    entry(int parent) : parent(parent), rank(0), user_count(1), comp_count(0) {}
  };

  std::vector<entry> entries;
  std::vector<int> citmappings;

  int add_entry() {
    int idx = entries.size();
    entries.push_back(idx);
    return idx;
  }

  int find(int x) {
    x = citmappings[x];
    int p = x;
    while (entries[p].parent != p) {
      p = entries[p].parent;
    }

    while (entries[x].parent != x) {
      int nextx = entries[x].parent;
      entries[x].parent = p;
      x = nextx;
    }

    return p;
  }

public:
  union_find(int count) {
    citmappings.reserve(count);
    entries.reserve(count);
    for (int i = 0; i < count; i++) {
      citmappings.push_back(add_entry());
    }
  }

  void reset(int c) {
    auto &cc = entries.at(find(c));
    cc.comp_count--;
    cc.user_count--;
    citmappings[c] = add_entry();
  }

  bool are_oonioned(int x, int y) { return find(x) == find(y); }

  void oonion(int x, int y) {
    x = find(x);
    y = find(y);

    if (x == y) {
      entries[x].comp_count++;
      return;
    }

    if (entries[x].rank < entries[y].rank) {
      std::swap(x, y);
    }

    entries[y].parent = x;
    if (entries[x].rank == entries[y].rank) {
      entries[x].rank++;
    }
    entries[x].comp_count += entries[y].comp_count + 1;
    entries[x].user_count += entries[y].user_count;
  }

  has_computer has(int c) {
    c = find(c);
    assert(entries[c].comp_count <= entries[c].user_count);
    if (entries[c].comp_count == entries[c].user_count) {
      return has_computer::yes;
    } else if (entries[c].comp_count == 0) {
      return has_computer::no;
    } else {
      return has_computer::maybe;
    }
  }
};

struct citizen {
  int component;
  citizen(int c) : component(c) {}
};

int main() {
  int n, q;
  scanf("%d %d", &n, &q);

  union_find uf(n);
  std::vector<char> retstr;

  for (int i = 0; i < q; i++) {
    int cmd = ' ';
    while (isspace(cmd)) {
      cmd = getchar();
    }
    switch (cmd) {
    case '+': {
      int a, b;
      scanf("%d %d", &a, &b);
      a--;
      b--;
      assert(uf.has(a) != has_computer::yes || uf.has(b) != has_computer::yes);
      uf.oonion(a, b);
    } break;
    case '-': {
      int c;
      scanf("%d", &c);
      c--;
      // Give a computer to everybody in our group,
      // then return our computer
      uf.reset(c);
    } break;
    case '?': {
      int d;
      scanf("%d", &d);
      d--;
      switch (uf.has(d)) {
      case has_computer::no:
        retstr.push_back('0');
        break;
      case has_computer::maybe:
        retstr.push_back('?');
        break;
      case has_computer::yes:
        retstr.push_back('1');
        break;
      }
    } break;
    default:
      assert(false);
    }
  }

  retstr.push_back('\n');
  fwrite(retstr.data(), retstr.size(), sizeof(char), stdout);

  return 0;
}