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
106
107
108
109
110
111
112
#include<bits/stdc++.h>
using namespace std;

int uf[1300009], status[1300009], siz[1300009], recalc[1300009], col[1300009], x;
vector<int> graf[1300009];

int find(int u)
{
	return (uf[u] == u ? u : uf[u] = find(uf[u]));
}

void Union(int u, int v)
{
	siz[find(v)] += siz[find(u)];
	uf[find(u)] = find(v);
	return;
}

void Unify(int u, int v)
{
	status[u] = status[v] = 2;
	graf[u].push_back(v);
	graf[v].push_back(u);
	Union(u, v);
	return;
}

void DFS(int u, int k)
{
	col[u] = 1;
	status[u] = k;
	uf[u] = u;
	siz[u] = 1;
	for(int i=0; i<graf[u].size(); i++) if(col[graf[u][i]] == 0) DFS(graf[u][i], k);
	graf[u].clear();
	col[u] = 0;
	return;
}

void add_edge()
{
	int a, b;
	cin>>a>>b;
	a = recalc[a];
	b = recalc[b];
	if(status[b] > status[a]) swap(a, b);			// status[a] >= status[b]
	if(status[a] == 0)
	{
		if(a == b) status[a] = 1;
		else Unify(a, b);
	}
	else if(status[a] == 1) status[b] = 1;			// status[b] = 0
	else if(status[a] == 2)
	{
		if(status[b] == 0) Unify(a, b);
		else if(status[b] == 1) DFS(a, 1);
		else if(status[b] == 2)
		{
			if(find(a) != find(b)) Unify(a, b);
			else DFS(a, 1);
		}
	}
	return;
}

void del()
{
	int a, b, c;
	cin>>a;
	b = recalc[a];
	if(status[b] == 1) status[b] = 0;
	else if(status[b] == 2)
	{
		siz[find(b)]--;
		if(siz[find(b)] == 1) DFS(b, 0);
		else
		{
			c = x;
			x++;
			uf[c] = recalc[c] = recalc[a] = recalc[b] = c;
			siz[c] = 1;
			status[c] = 0;
		}
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, q, a;
	char c;
	cin>>n>>q;
	for(int i=1; i<=n; i++) uf[i] = recalc[i] = i;
	for(int i=1; i<=n; i++) siz[i] = 1;
	x = n + 1;
	for(int i=1; i<=q; i++)
	{
		cin>>c;
		if(c == '+') add_edge();
		else if(c == '-') del();
		else
		{
			cin>>a;
			a = recalc[a];
			if(status[a] == 2) cout<<"?";
			else cout<<status[a];
		}
	}
	return 0;
}