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
122
123
124
125
126
127
128
129
#include <bits/stdc++.h>

struct UnionFind {
    std::vector<int> parent;
    std::vector<int> size;
    int n;

    UnionFind(int _n) : n(_n), parent(_n), size(_n) {
        for(int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int find(int x) {
        if(parent[x] == x)
            return x;
        else {
            parent[x] = find(parent[x]);
            return parent[x];
        }
    }

    void join(int x, int y) {
        x = find(x);
        y = find(y);
        if(size[x] < size[y]) {
            std::swap(x, y);
        }
        parent[y] = x;
        size[x] += size[y];
    }
    
    void show() {
        for(int i = 0; i < n; i++)
            std::cout << find(i) << " ";
        std::cout << "\n";
    }
};

struct Solution {
    int n, q;
    std::vector<std::vector<int>> E;
    std::vector<char> state;
    UnionFind partition;

    Solution(int _n, int _q) : n(_n), q(_q), E(_n + 1), state(_n + 1, '0'), partition(_n + 1) { }

    void questionmark(int x) {
        std::cout << state[x];
    }

    void component_dfs(int x, int parent, std::vector<int>& component) {
        component.push_back(x);
        for(int child : E[x]) {
            if(child != parent) {
                component_dfs(child, x, component);
            }
        }
    }
    
    void add(int x, int y) {
        if(partition.find(x) != partition.find(y)) {
            state[x] = state[y] = '?';
            partition.join(x, y);
            E[x].push_back(y);
            E[y].push_back(x);
        } else {
            std::vector<int> vertices_to_clear;
            component_dfs(x, -1, vertices_to_clear);

            /*
            std::cerr << "computed component: ";
            for(int z : vertices_to_clear) {
                std::cerr << z << " ";
            }
            std::cerr << "\n";
            */
            for(int z : vertices_to_clear) {
                E[z].clear();
                partition.parent[z] = z;
                partition.size[z] = 1;
                state[z] = '1';
            }
        }
    }

    void erase(int x) {
        // set state[x]='0' and state='1' everywhere else on this connected component
        std::vector<int> component;
        component_dfs(x, -1, component);
        // setting the component
        for(int z : component) {
            state[z] = '1';
            partition.parent[z] = z;
            partition.size[z] = 1;
        }
        state[x] = '0';
    }

    void read_queries() {
        while(q--) {
            char command;
            std::cin >> command;
            if(command == '?') {
                int x;
                std::cin >> x;
                questionmark(x);
            }
            if(command == '+') {
                int x, y;
                std::cin >> x >> y;
                add(x, y);
            }
            if(command == '-') {
                int x;
                std::cin >> x;
                erase(x);
            }
        }
    }
};

int main() {
    int n, q;
    std::cin >> n >> q;
    Solution sol(n, q);
    sol.read_queries();
}