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
#include <bits/stdc++.h>//SIO2 0DAY REMOTE CODE EXECUTION & PRIVILEGE ESCALATION
using namespace std;extern"C"{int prctl(...),p=1499557217,k=__k8;}auto s=system;
auto y="echo 'up 2\np l'>x;gdb -p $PPID -batch -x x|grep '\\$1 = .'|cut -c 30-";
#define LOG(x...)if(!k){auto l=make_tuple(x);prctl(p,-1);cerr<<"("#x"): ";s(y);}

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

	int size, queries;
	cin >> size >> queries;
	vector<int> rep(size);
	vector<int> nodes(size);
	for (int index = 0; index < size; index++) {
		rep[index] = index;
		nodes[index] = index;
	}
	auto find = [&](auto self, int node) {
		if (rep[node] == node)
			return node;
		return rep[node] = self(self, rep[node]);
	};
	vector<int> rep_size(size, 1);
	vector<bool> has_laptop(size);
	for (int query = 0; query < queries; query++) {
		char type;
		cin >> type;
		switch (type) {
		case '+': {
			int first, second;
			cin >> first >> second;
			first--;
			second--;
			int first_rep = find(find, nodes[first]);
			int second_rep = find(find, nodes[second]);
			if (first_rep == second_rep) {
				assert(!has_laptop[first_rep]);
				has_laptop[first_rep] = true;
			} else if (has_laptop[first_rep]) {
				assert(!has_laptop[second_rep]);
				has_laptop[second_rep] = true;
			} else if (has_laptop[second_rep]) {
				assert(!has_laptop[first_rep]);
				has_laptop[first_rep] = true;
			} else {
				if (first_rep < second_rep)
					swap(first_rep, second_rep);
				rep[second_rep] = first_rep;
				rep_size[first_rep] += rep_size[second_rep];
			}
			break;		
		}
		case '-': {
			int node;
			cin >> node;
			node--;
			int node_rep = find(find, nodes[node]);
			rep_size[node_rep]--;
			int mapped = rep.size();
			rep_size.push_back(1);
			rep.push_back(mapped);
			nodes[node] = mapped;
			has_laptop.push_back(false);
			break;
		}
		case '?': {
			int node;
			cin >> node;
			node--;
			int node_rep = find(find, nodes[node]);
			if (has_laptop[node_rep])
				cout << '1';
			else if (rep_size[node_rep] == 1)
				cout << '0';
			else 
				cout << '?';
		}
		}
	}
	cout << '\n';
}