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
130
131
132
133
134
135
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <queue>

using namespace std;

void moveToYes(int x, unordered_map<int, set<int>> &nodes, set<int> &yes) {
    queue<int> todo;
    todo.push(x);

    while(!todo.empty()) {
        int t = todo.front();
        todo.pop();
        yes.insert(t);

        for(int tt : nodes[t]) {
            if(yes.find(tt) == yes.end()) {
                todo.push(tt);
            }
        }

        nodes.erase(t);
    }
}

bool isCycle(int x, unordered_map<int, set<int>> &nodes) {
    queue<int> todo;
    queue<int> anc;
    set<int> visited;

    visited.insert(x);
    todo.push(x);
    anc.push(-1);

    while(!todo.empty()) {
        int t = todo.front();
        todo.pop();

        int a = anc.front();
        anc.pop();

        for(int tt : nodes[t]) {
            if(tt != a) {

                if(visited.find(tt) != visited.end()) {
                    return true;
                }

                todo.push(tt);
                anc.push(t);
                visited.insert(tt);
            }
        }
    }

    return false;
}

int main() {

    unordered_map<int, set<int>> nodes;
    set<int> yes;
    int n, q;
    int a, b;
    char action;

    scanf(" %d", &n);
    scanf(" %d", &q);

    while(q-- > 0) {
        scanf(" %c", &action);

        if(action == '?') {
            scanf(" %d", &a);

            if(yes.find(a) != yes.end()) {
                printf("1");
                continue;
            }

            bool any = nodes.find(a) != nodes.end() && !nodes[a].empty();
            if(!any) {
                printf("0");
            } else {
                printf("?");
            }
        } else if(action == '+') {
            scanf(" %d", &a);
            scanf(" %d", &b);

            if(a == b) {
                moveToYes(a, nodes, yes);
            } else if(yes.find(a) != yes.end()) {
                moveToYes(b, nodes, yes);
            } 
            else if(yes.find(b) != yes.end()) {
                moveToYes(a, nodes, yes);
            } 
            else {
                set<int> aLinks = nodes[a];
                if(aLinks.find(b) != aLinks.end()) {
                    moveToYes(a, nodes, yes);
                } else {
                    nodes[a].insert(b);
                    nodes[b].insert(a);

                    if(isCycle(a, nodes)) {
                        moveToYes(a, nodes, yes);
                    }
                }
            }
        } else if(action == '-') {
            scanf(" %d", &a);

            if(yes.find(a) != yes.end()) {
                yes.erase(a);
            } else {
                for(int aa : nodes[a]) {
                    nodes[aa].erase(a);
                }

                nodes.erase(a);
            }
        }
    };

    return 0;
}