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
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int((x).size()))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define gc getchar_unlocked
#define pc putchar_unlocked
using namespace std;

void wczytaj(int &a){
	int c = gc();
	while(c < '0' || c > '9') c = gc();
	for(a = 0; c >= '0' && c <= '9'; c = gc()) a = 10*a+c-'0';
}
void znak(int &c){
	c = gc();
	while(c!='?' && c!='+' && c!='-') c = gc();
}

struct znajdz_i_polacz{
	vector<int> r, rozm;
	znajdz_i_polacz(int n){
		r.resize(n+1);
		rozm.resize(n+1, 1);
		FOR(i, 0, n) r[i] = i;
	}
	int f(int x){
		if(r[x] != x) r[x] = f(r[x]);
		return r[x];
	}
	void u(int a, int b){
		a = f(a), b = f(b);
		if(rozm[a] > rozm[b]) swap(a, b);
		if(a != b) r[a] = b, rozm[b] += rozm[a];
	}
};

void solve(){
	int n, q;
	wczytaj(n), wczytaj(q);
	
	znajdz_i_polacz janusz(n+q);
	vector<bool> smierc(n+q+1, 0);
	vector<int> nr(n+1);
	FOR(i, 1, n) nr[i] = i;
	
	FOR(numer_akt, n+1, n+q){
		int c;
		znak(c);
		if(c == '+'){
			int a, b;
			wczytaj(a), wczytaj(b);
			int fa = janusz.f(nr[a]);
			int fb = janusz.f(nr[b]);
			if(nr[a] && smierc[fa]) nr[a] = 0;
			if(nr[b] && smierc[fb]) nr[b] = 0;
			if(!nr[a] || !nr[b] || fa==fb) smierc[fa] = smierc[fb] = 1;
			else janusz.u(fa, fb);
		}
		else if(c == '-'){
			int a;
			wczytaj(a);
			int fa = janusz.f(nr[a]);
			if(nr[a] && smierc[fa]) nr[a] = 0;
			if(nr[a]) --janusz.rozm[fa];
			nr[a] = numer_akt;
		}
		else{
			int a;
			wczytaj(a);
			int fa = janusz.f(nr[a]);
			if(nr[a] && smierc[fa]) nr[a] = 0;
			if(!nr[a]) pc('1');
			else if(janusz.rozm[fa] == 1) pc('0');
			else pc('?');
		}
	}
}

int main(){
	solve();
	return 0;
}