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
#include<iostream>
#include<vector>
#include<unordered_set>
int main() {
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0);
	int n, m, a, b, p;
	std::cin >> n >> m;
	std::vector<int> w(n);
	std::vector<std::unordered_set<int>> s;
	std::unordered_set<int>::iterator itr;
	char x;
	for (int i = 0; i < m; i++) {
		std::cin >> x;
		if (x == '+') {
			std::cin >> a >> b; a--; b--;
			if (a == b) {
				if (w[a] == 0)
					w[a] = -1;
				else {
					p = w[a];
					for (itr = s[p - 1].begin(); itr != s[p - 1].end(); itr++) {
						w[*itr] = -1;
					}
				}
			}
			else
				if (w[a] == 0 and w[b] == 0) {
					s.resize(s.size() + 1);
					s[s.size() - 1].insert(a);
					s[s.size() - 1].insert(b);
					w[a] = s.size();
					w[b] = s.size();
				}
				else if (w[a] == 0 and w[b] == -1) {
					w[a] = -1;
				}
				else if (w[b] == 0 and w[a] == -1) {
					w[b] = -1;
				}
				else if (w[a] == 0) {
					w[a] = w[b];
					s[w[a] - 1].insert(a);
				}
				else if (w[b] == 0) {
					w[b] = w[a];
					s[w[a] - 1].insert(b);
				}
				else {
					if (w[a] == -1) {
						p = w[b];
						for (itr = s[p - 1].begin(); itr != s[p - 1].end(); itr++) {
							w[*itr] = -1;
						}
					}
					else if (w[b] == -1) {
						p = w[a];
						for (itr = s[p - 1].begin(); itr != s[p - 1].end(); itr++) {
							w[*itr] = -1;
						}
					}
					else {
						if (w[a] == w[b]) {
							p = w[a];
							for (itr = s[p - 1].begin(); itr != s[p - 1].end(); itr++) {
								w[*itr] = -1;
							}
						}
						else {
							if (s[w[a] - 1].size() < s[w[b] - 1].size()) {
								std::swap(a, b);
							}
							p = w[b];
							for (itr = s[p - 1].begin(); itr != s[p - 1].end(); itr++) {
								w[*itr] = w[a];
								s[w[a] - 1].insert(*itr);
							}
						}
					}
				}
		}
		else if (x == '?') {
			std::cin >> a; a--;
			if (w[a] == 0) std::cout << "0";
			else if (w[a] == -1) std::cout << "1";
			else std::cout << "?";
		}
		else {
			std::cin >> a; a--;
			if (w[a] == -1)
				w[a] = 0;
			else {
				p = w[a];
				s[p - 1].erase(s[p - 1].find(a));
				if (s[p - 1].size() == 1) {
					itr = s[p - 1].begin();
					w[*itr] = 0;
				}
				w[a] = 0;
			}

		}
	}

}