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
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

struct UF{
    int rozm=1;
    bool czypelne=false;
    UF* rod = nullptr;
    UF* find(){
        if(rod==nullptr) return this; else return rod->find();
    }
    static void join(UF* a, UF* b){
        a=a->find();
        b=b->find();
        if (a == b) {
            a->czypelne=true;
            return;
        }
        if (a->rozm < b->rozm) swap(a, b);
        a->rozm += b->rozm;
        a->czypelne = (a->czypelne)||(b->czypelne);
        b->rod=a;
    }
};

const int N=300000;
UF* chlopy[N];
void _plus(int a, int b){
    a--;
    b--;
    UF::join(chlopy[a], chlopy[b]);
}
void _minus(int c){
    c--;
    chlopy[c]->find()->rozm--;
    chlopy[c] = new UF();
}
char _pyt(int d){
    d--;
    if(chlopy[d]->find()->czypelne) return '1'; ///na pewno ma
    if(chlopy[d]->find()->rozm==1) return '0'; ///na pewno nie ma
    return '?'; ///mo¿e ma, a mo¿e nie
}

int main()
{
    cin.sync_with_stdio(0); cin.tie(0);
    string odp="";
    int n, q;
    scanf("%d %d", &n, &q);
    for(int i=0; i<n; i++)
        chlopy[i]=new UF();
    char cpom;
    int a, b, c, d;
    for(int i=0; i<q; i++){
        cpom=0;
        while(cpom!='+' && cpom!= '-' && cpom!='?') scanf("%c", &cpom);
        if(cpom=='+'){
            scanf("%d %d", &a, &b);
            _plus(a, b);
        } else
        if(cpom=='-'){
            scanf("%d", &c);
            _minus(c);
        } else
        if(cpom=='?'){
            scanf("%d", &d);
            odp+=_pyt(d);
        }
    }
    cout << odp;
    return 0;
}