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
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <iostream>
#include <vector>

struct node {
    node(int next): next(next) {}
    int next;
    bool and_one = false;
    int count = 1;
};

struct xd {
    xd(int n, int q) {
        uf.reserve(2 * n + q + 1);
        uf.emplace_back(-1);
        for (int i = 0; i < n; ++i) {
            uf.emplace_back(i + n + 1);
        }
        for (int i = 0; i < n; ++i) {
            uf.emplace_back(i + n + 1);
        }
    }

    void deliver(int a, int b) {
        // std::cerr << "+";
        auto aa = resolve(a);
        auto bb = resolve(b);
        if (aa != bb) {
            uf[bb].next = aa;
            uf[aa].and_one |= uf[bb].and_one;
            uf[aa].count += uf[bb].count;
        } else {
            uf[aa].and_one = true;
        }
        // if (rewire(b, aa)) {
        //     uf[aa].and_one |= uf[b].and_one;
        //     uf[aa].count += uf[b].count;
        // } else {
        //     uf[aa].and_one = true;
        // }
    }

    void destroy(int c) {
        // std::cerr << "-";
        uf[resolve(c)].count -= 1;
        uf.emplace_back(uf.size());
        // std::cerr << "(" << uf.back().count << ")";
        uf[c].next = uf.size() - 1;
        // std::cerr << "(" << uf[resolve(c)].count << ")";
        // std::cerr << "(" << uf.size() - 1 << " " << resolve(c) << " " << uf[c].next << ")";
    }

    char query(int d) {
        // std::cerr << "Q";
        auto &fin = uf[resolve(d)];
        if (fin.and_one) { return '1'; }
        if (fin.count == 1) { return '0'; }
        return '?';
    }

    int resolve(int i) {
        // std::cerr << "{" << i << "}";
        if (uf[i].next == i) {
            return i;
        }
        int next = resolve(uf[i].next);
        uf[i].next = next;
        return next;
    }

    // int rewire(int from, int to) {
    //     // std::cerr << "[" << from << "]";
    //     if (uf[from].next == from) {
    //         uf[from].next = to;
    //         return from;
    //     }
    //     if (uf[from].next == to) {
    //         return 0;
    //     }
    //     auto res = rewire(uf[from].next, to);
    //     uf[from].next = to;
    //     return res;
    // }

    std::vector<node> uf;
};

int main() {
    int n, q;
    std::cin >> n >> q;

    xd xd(n, q);
    for (int i = 0; i < q; ++i) {
        std::string type;
        std::cin >> type;
        if (type == "?") {
            int d;
            std::cin >> d;
            std::cout << xd.query(d);
            // std::cerr << type << "\n";
        } else if (type == "+") {
            int a, b;
            std::cin >> a >> b;
            xd.deliver(a, b);
        // std::cerr << "after + " << a << " " << b << ":\n";
        for (int i = 1; i <= n; ++i) {
            // std::cerr << i << "(" << xd.uf[xd.resolve(i)].count << " " << xd.uf[xd.resolve(i)].and_one << ")";
        }
        // std::cerr << "\n";
        } else if (type == "-") {
            int c;
            std::cin >> c;
            xd.destroy(c);
        // std::cerr << "after - " << c << ":\n";
        for (int i = 1; i <= n; ++i) {
            // std::cerr << i << "(" << xd.uf[xd.resolve(i)].count << " " << xd.uf[xd.resolve(i)].and_one << ")";
        }
        // std::cerr << "\n";
        }
    }
    std::cout << "\n";
}