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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ssize(a) ((int)(a.size()))

int fau(int ter, vector<int>&nal)
{
    if(nal[ter] == ter)
        return ter;
    nal[ter] = fau(nal[ter], nal);
    return nal[ter];
}

int fastin()
{
    int ret = 0, gc = getchar_unlocked() - '0';
    while(gc < 0 || gc > 9)
        gc = getchar_unlocked() - '0';
    while(gc >= 0 && gc <= 9)
    {
        ret = ret * 10 + gc;
        gc = getchar_unlocked() - '0';
    }
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    n = fastin();
    q = fastin();
    vector<int>nal(n + 1, 0), przenr(n + 1, 0);
    vector<int>wszma(n + 1, 1), ilpol(n + 1, 0);
    int ilej = n;
    auto nowy = [&](int a)
    {
        przenr[a] = ++ilej;
        nal.push_back(ilej);
        wszma.push_back(1);
        ilpol.push_back(0);
    };

    for(int i = 1; i <= n; ++i)
        nal[i] = przenr[i] = i;

    for(int i = 0; i < q; ++i)
    {
        char c = getchar_unlocked();
        while(c != '?' && c != '-' && c != '+')
            c = getchar_unlocked();
        if(c == '?')
        {
            int a;
            a = fastin();
            a = fau(przenr[a], nal);
            if(wszma[a] == ilpol[a])
                putchar('1');
            else if(ilpol[a])
                putchar('?');
            else
                putchar('0');
        }
        else if(c == '-')
        {
            int a;
            a = fastin();
            int b = fau(przenr[a], nal);
            --ilpol[b];
            --wszma[b];
            nowy(a);
        }
        else
        {
            int a, b;
            a = fastin();
            b = fastin();
            a = fau(przenr[a], nal);
            b = fau(przenr[b], nal);
            if(a == b)
                ++ilpol[a];
            else
            {
                nal[b] = a;
                ilpol[a] += ilpol[b] + 1;
                wszma[a] += wszma[b];
            }
        }
    }
    return 0;
}