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
#include <iostream>
#include <vector>

using namespace std;

struct para{
    int a,b;
};

vector<vector<pair<para,int>>> zbiory;

bool operator==(para a,para b)
{
    return a.a == b.a && a.b == b.b;
}

para find(para x)
{
    if(zbiory[x.a][x.b].first.a!=x.a || zbiory[x.a][x.b].first.b!=x.b)
    {
        find(zbiory[x.a][x.b].first);
        zbiory[x.a][x.b].first=zbiory[zbiory[x.a][x.b].first.a][zbiory[x.a][x.b].first.b].first;
    }

    return zbiory[x.a][x.b].first;
}

void unionek(para x, para y)
{
    x = find(x);
    y = find(y);

    if(x == para {0,0})
        swap(x,y);

    zbiory[y.a][y.b].second+=zbiory[x.a][x.b].second;
    zbiory[x.a][x.b].first=zbiory[y.a][y.b].first;
    zbiory[x.a][x.b].second=0;
}

para k(int x)
{
    return {x,int(zbiory[x].size())-1};
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,m;
    cin >> n >> m;

    for(int i = 0;i<=n;i++)
        zbiory.push_back({{{i,0},1}});

    for(int i = 0;i<m;i++)
    {
        char p;
        int x,y;

        cin >> p;

        if(p == '?')
        {
            cin >> x;

            if(find(k(x)) == para {0,0})
                cout << 1;
            else if(zbiory[find(k(x)).a][find(k(x)).b].second > 1)
                cout <<'?';
            else
                cout << 0;
        } else if(p == '+')
        {
            cin >> x >> y;

            if(find(k(x)) == find(k(y)))
            {
                unionek(k(x),{0,0});
                unionek(k(y),{0,0});
            }
            else
                unionek(k(x),k(y));
        } else if(p == '-')
        {
            cin >> x;

            zbiory[find(k(x)).a][find(k(x)).b].second--;

            zbiory[x].push_back({{x,int(zbiory[x].size())},1});
        }
    }
}