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
#include <bits/stdc++.h>
using std::cin, std::cout, std::vector;

void init_io() {
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}

enum Answer {
  answer_no,
  answer_yes,
  answer_unknown,
};

const char answer_name[3] = {'0', '1', '?'};

constexpr unsigned index_none = -1u;

struct Group {
  unsigned num_nodes = 1;
  unsigned num_tokens = 0;
  unsigned rank = 0;
};

class Graph {
public:
  explicit Graph(const unsigned n, const unsigned max_removals) {
    num_nodes = n;
    const unsigned max_nodes = n + max_removals;

    person_to_node.reserve(n);
    for (unsigned i=0; i<n; ++i) person_to_node.push_back(i);

    parent.reserve(max_nodes);
    parent.assign(num_nodes, index_none);

    groups.reserve(max_nodes);
    groups.resize(num_nodes);
  }

  void add_token(const unsigned pa, const unsigned pb) {
    unsigned a = find(pa);
    unsigned b = find(pb);
    if (groups[a].rank < groups[b].rank) std::swap(a, b);
    Group &ga = groups[a];
    const Group &gb = groups[b];
    if (a != b) {
      parent[b] = a;
      ga.num_nodes += gb.num_nodes;
      ga.num_tokens += gb.num_tokens;
      if (ga.rank == gb.rank) ga.rank += 1;
    }
    assert(ga.num_tokens < ga.num_nodes);
    ga.num_tokens += 1;
  }

  void remove_token(const unsigned pa) {
    const unsigned a = find(pa);
    Group &ga = groups[a];
    assert(ga.num_tokens > 0);
    ga.num_nodes -= 1;
    ga.num_tokens -= 1;

    // allocate a new node
    parent.push_back(index_none);
    groups.emplace_back();
    person_to_node[pa] = num_nodes;
    ++num_nodes;
  }

  Answer has_token(const unsigned pa) {
    const unsigned a = find(pa);
    const Group &ga = groups[a];
    if (ga.num_tokens == 0) {
      return answer_no;
    } else if (ga.num_tokens == ga.num_nodes) {
      return answer_yes;
    } else {
      return answer_unknown;
    }
  }

private:
  unsigned find(const unsigned pa) {
    unsigned a = person_to_node[pa];
    unsigned b = a;
    for (;;) {
      const unsigned p = parent[b];
      if (p == index_none) break;
      b = p;
    }

    while (a != b) {
      const unsigned p = parent[a];
      parent[a] = b;
      a = p;
    }

    return b;
  }

  unsigned num_nodes;
  vector<unsigned> person_to_node;
  vector<unsigned> parent;
  vector<Group> groups;
};

int main() {
  init_io();

  unsigned n, num_queries;
  cin >> n >> num_queries;
  
  Graph graph(n, num_queries);
  for (unsigned i = 0; i < num_queries; ++i) {
    char op;
    cin >> op;
    if (op == '+') {
      unsigned a, b;
      cin >> a >> b;
      --a; --b;
      graph.add_token(a, b);
    } else if (op == '-') {
      unsigned a;
      cin >> a;
      --a;
      graph.remove_token(a);
    } else if (op == '?') {
      unsigned a;
      cin >> a;
      --a;
      const Answer answer = graph.has_token(a);
      cout << answer_name[answer];
    } else {
      throw 0;
    }
  }
  cout << "\n";
}