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
#include <bits/stdc++.h>

using namespace std;

vector <int> m, kompy(2);
vector <set<int>> sety(2);

void daj_kompy(int ai) {
	for (auto i : sety[m[ai]])
		m[i] = 1;
}

void polacz_sety(int ai, int bi) {
	if (m[ai] == 0) { 
		sety[m[bi]].insert(ai);
		++kompy[m[bi]];
		m[ai] = m[bi];
	}
	if (m[bi] == 0) { 
		sety[m[ai]].insert(bi);
		++kompy[m[ai]];
		m[bi] = m[ai];
	}
	if (kompy[m[ai]] >= kompy[m[bi]]) { 
		for (auto i: sety[m[bi]]){
			sety[m[ai]].insert(i);
			m[i] = m[ai];
		}
		kompy[m[ai]] += kompy[m[bi]];
	}
	else  { 
		for (auto i: sety[m[ai]]){
			sety[m[bi]].insert(i);
			m[i] = m[bi];
		}
		kompy[m[bi]] += kompy[m[ai]];
	}
		
}

int main (){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, q, ai, bi;
	char c;
	cin >> n >> q;
	//vector <int>
	m.resize(n + 1);
	//vector <set<int>> sety(2);
	while (q--) {
		cin >> c >> ai;
		switch (c) {
			case '+' :
				cin >> bi;
				//cout << "daje komputer dla " << ai << " i " << bi << endl;
				if (ai == bi) {
					if (m[ai] < 2) m[ai] = 1; //drugi komputer, niemożliwe?
					else { //jest w secie i dodaje 1 kompa
						//sety[m[ai]].erase(ai);
						//if (sety[m[ai]].size() >= kompy[m[ai]]) 
						daj_kompy(ai);//sety[m[ai]]);
					}
				}
				else if (m[ai] == 0 and m[bi] == 0) {
					int nowy = kompy.size(); //nowy set;
					kompy.push_back(1);
					sety.push_back(set<int>{ai, bi});
					//sety[nowy].insert(ai);
					//sety[nowy].insert(bi);
					m[ai] = m[bi] = nowy;
				}
				else if (m[ai] == 1) {// dostaje drugi
					if (m[bi] == 0) m[bi] = 1;
					else daj_kompy(bi); //dla seta m[bi]
				}
				else if (m[bi] == 1) { //dostaje drugi
					if (m[ai] == 0) m[ai] = 1;
					else daj_kompy(ai); //dla seta m[ai]
				}
				else if (m[ai] == m[bi]) daj_kompy(ai); //obaj są w tym samym secie
				else polacz_sety(ai, bi); //nawet jak jest m[ai] lub m[bi] == 0
				
				break;
			case '-' :
				//cout << "zlom " << ai << endl;
				if (m[ai] > 1) {
					sety[m[ai]].erase(ai);
					if (sety[m[ai]].size() == 1)
						m[*sety[m[ai]].begin()] = 0;
					--kompy[m[ai]];
				}
				m[ai] = 0;
				break;
			case '?' :
				//cout << "zapytuje o " << ai << endl;
				if (m[ai] > 1) cout << '?';
				else cout << m[ai];
				break;
			}
		}
	return 0;
}