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
#include <bits/stdc++.h>
using namespace std;
const int N=3e6;
vector<int>pol[N];
int odw[N], nr, pewniaczek[N], kon[N], rev[N], node=1;
int rep[N], ile[N], sum[N];
int find(int x)
{
	if (rep[x]!=x) rep[x]=find(rep[x]);
	return rep[x];
}
void uni(int a, int b)
{
	a=find(a);
	b=find(b);
	if (a==b) return;
	if (ile[a]<ile[b]) swap(a, b);
	rep[b]=a;
	ile[a]+=ile[b];
	sum[a]+=sum[b];
}
void dfs(int w, int k, int c)
{
	odw[w]=c;
	for (auto i : pol[w])
		if (odw[i] != c)
			dfs(i, k, c);
	pewniaczek[rev[w]]=1;
	kon[rev[w]]=0;
	rev[w]=0;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, q; cin>>n>>q;
	for (int tt=0; tt<q; tt++)
	{
		char c; cin>>c;
		if (c == '+')
		{
			int a, b; cin>>a>>b;
			if (!kon[a])
			{
				rep[node]=node, ile[node]=1, sum[node]=1;
				rev[node]=a, kon[a]=node++;
			}
			if (!kon[b])
			{
				rep[node]=node, ile[node]=1, sum[node]=1;
				rev[node]=b, kon[b]=node++;
			}
			pol[kon[a]].push_back(kon[b]);
			pol[kon[b]].push_back(kon[a]);
			if (pewniaczek[a] || pewniaczek[b] || find(kon[a])==find(kon[b]))
			{
				//~ cout<<"PEWNIAK "<<a<<" "<<b<<endl;
				dfs(kon[a], b, ++nr);
			}
			else uni(kon[a], kon[b]);
		}
		if (c == '-')
		{
			int a; cin>>a;
			pewniaczek[a]=0;
			rev[kon[a]]=0;
			sum[find(kon[a])]--;
			kon[a]=0;
		}
		if (c == '?')
		{
			int a; cin>>a;
			if (pewniaczek[a]) cout<<1;
			else if (kon[a] && sum[find(kon[a])]>1) cout<<"?";
			else cout<<0;
			//~ cout<<"\nXD "<<a<<" "<<kon[a]<<" "<<sum(kon[a], ++nr)<<endl;
		}
	}
	cout<<"\n";
}