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
#include <cstdio>
#include <vector>
#include <algorithm>

#define REP(a, n) for (int a = 0; a < (n); ++a)

using namespace std;

//////////////////////

#define ILE 300001

int N, Q;
vector<int> wolne;
int num[ILE], poprz[ILE], nast[ILE];
int rozm[ILE], silna[ILE];

void polacz(int a, int b) {
    if (num[a] == num[b]) {
        silna[num[a]] = 1;
        return;
    }
    if (rozm[num[a]] > rozm[num[b]])
        swap(a, b);
    if (silna[num[a]])
        silna[num[b]] = 1;
    rozm[num[b]] += rozm[num[a]];
    swap(nast[a], nast[b]);
    swap(poprz[nast[a]], poprz[nast[b]]);
    wolne.push_back(num[a]);
    for (int c = nast[b]; num[c] != num[b]; c = nast[c])
        num[c] = num[b];
}

void usun(int a) {
    if (rozm[num[a]] > 1) {
        nast[poprz[a]] = nast[a];
        poprz[nast[a]] = poprz[a];
        --rozm[num[a]];
        int x = wolne.back();
        wolne.pop_back();
        num[a] = x;
        poprz[a] = nast[a] = a;
        silna[x] = 0;
        rozm[x] = 1;
    }
    else {
        silna[num[a]] = 0;
    }
}

int main() {
    scanf("%d%d", &N, &Q);
    REP(a, N) {
        rozm[a] = 1;
        num[a] = poprz[a] = nast[a] = a;
    }
    REP(q, Q) {
        char ch;
        int a, b;
        scanf(" %c%d", &ch, &a);
        --a;
        if (ch == '+') {
            scanf("%d", &b);
            --b;
            polacz(a, b);
        }
        else
        if (ch == '-') {
            usun(a);
        }
        else {
            printf("%c", silna[num[a]] ? '1' : rozm[num[a]] > 1 ? '?' : '0');
        }
    }
    printf("\n");
}