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
#include <cstdio>
#include <list>
#define MAKSN 300010
#define MAKSQ 1000010
using namespace std;
list<int> zbiory[MAKSQ];
int rozmiar[MAKSQ];
int kolor[MAKSQ];

list<int>::iterator element[MAKSN];
int grupa[MAKSN];
int N;

void dodaj_nowy(int x)
{
	zbiory[N].push_back(x);
	rozmiar[N]=1;
	kolor[N]=0;
	element[x]=prev(zbiory[N].end());
	grupa[x]=N;
	N++;
}

void zlacz(int a, int b)
{
	int gA=grupa[a]; int gB=grupa[b];
	if(gA==gB)
	{
		kolor[gA]=1;
		return;
	}
	if(rozmiar[gA]<=rozmiar[gB])swap(gA, gB);
	kolor[gA]=kolor[gA]+kolor[gB];
	while(!zbiory[gB].empty())
	{
		int x=zbiory[gB].back(); zbiory[gB].pop_back();
		zbiory[gA].push_back(x);
		rozmiar[gA]++;
		element[x]=prev(zbiory[gA].end());
		grupa[x]=gA;
	}
}

void usun(int x)
{
	int g=grupa[x];
	zbiory[g].erase(element[x]);
	rozmiar[g]--;
	dodaj_nowy(x);
}

int main()
{
	int n,q;
	scanf("%d %d",&n,&q);
	N=0;
	for(int i=1;i<=n;i++)dodaj_nowy(i);
	for(int i=0;i<q;i++)
	{
		char s[3];
		int a,b;
		scanf("%s",s);
		if(s[0]=='+')
		{
			scanf("%d %d",&a,&b);
			zlacz(a, b);
		}
		else if(s[0]=='-')
		{
			scanf("%d",&a);
			usun(a);
		}
		else if(s[0]=='?')
		{
			scanf("%d",&a);
			int gA=grupa[a];
			if(kolor[gA]==1)printf("1");
			else if(rozmiar[gA]==1)printf("0");
			else printf("?");
		}
	}
	printf("\n");
}