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
#include <iostream>
#include <vector>

using namespace std;

constexpr int maxN = 300'007;
constexpr int maxQueries = 1'000'007;

int n, queries;

bool full[maxN + maxQueries];
vector<int> spojna[maxN + maxQueries];
int rep[maxN];
int realMembers[maxN + maxQueries];

int GROUPIDGIVER;

void connect(int a, int b) {
  if (rep[a] == rep[b]) {
    full[rep[a]] = true;
    return;
  }

  int GROUPA = rep[a];
  int GROUPB = rep[b];
  if (spojna[GROUPA].size() < spojna[GROUPB].size()) {
    swap(GROUPA, GROUPB);
  }

  for (int& node : spojna[GROUPB]) {
    if (rep[node] != GROUPB) { // it got isolated out of it
      continue; // lets just ignore it
    }
    rep[node] = GROUPA;
    spojna[GROUPA].push_back(node);

    realMembers[GROUPA]++;
  }
  spojna[GROUPB].clear();
  realMembers[GROUPB] = 0;

  full[GROUPA] = (full[GROUPA] || full[GROUPB]);
}

void isolate(int node) {
  realMembers[rep[node]]--;

  spojna[GROUPIDGIVER].push_back(node);
  rep[node] = GROUPIDGIVER;
  realMembers[GROUPIDGIVER] = 1;

  GROUPIDGIVER++;
}

void answer(int node) { // does not care if leftovers
  if (full[rep[node]]) {
    cout << '1';
    return;
  }

  if (realMembers[rep[node]] == 1) {
    cout << '0';
    return;
  }

  cout << '?';
  return;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  cin >> n >> queries;
  GROUPIDGIVER = n+1;

  for (int i = 1; i <= n; i++) {
    rep[i] = i;
    full[i] = false;
    spojna[i].push_back(i);
    realMembers[i] = 1;
  }

  for (int i = 0; i < queries; i++) {
    char type;
    cin >> type;
    if (type=='?') {
      int node;
      cin >> node;
      answer(node);
      continue;
    }
    if (type == '+') {
      int a, b;
      cin >> a >> b;
      connect(a, b);
    } else {
      int node;
      cin >> node;
      isolate(node);
    }
  }

  cout << '\n';

  return 0;
}