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
#include <bits/stdc++.h>
using namespace std;

int next_group_id;
map<int, int> group_size;
vector<int> visited;

void relax_dfs(int u, vector<vector<pair<int, int>>>& graph, vector<int>& ans, vector<int>& group_id, int s){
    group_id[u] = next_group_id; group_size[group_id[u]]++; next_group_id++;
    ans[u] = 1;
    for(auto v: graph[u]){
        if(visited[v.first] == s || v.first == -1) continue;
        visited[v.first] = s;
        relax_dfs(v.first, graph, ans, group_id, s);
    }
    graph[u].clear();
}

void merge(int u, int p, vector<vector<pair<int, int>>>& graph, vector<int>& group_id){
    for(auto v: graph[u]){
        if(v.first == p || v.first == -1) continue;
        if(group_id[u] != group_id[v.first]) group_size[group_id[u]]++;
        group_id[v.first] = group_id[u];
        merge(v.first, u, graph, group_id);
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cout.tie(0); cin.tie(0);
    int n, q; cin>>n>>q;
    //----------------------
    vector<int> ans(n+1, 0), group_id(n+1, 0); for(int i=0; i<=n; i++){group_id[i] = i; group_size[i]++;}
    vector<vector<pair<int, int>>> graph(n+1, vector<pair<int, int>>());
    vector<int> visited2(n+1, 0);
    visited = visited2;
    next_group_id = n+1;
    while(q--){
        char type; cin>>type;
        int u, v;
        if(type == '?'){
            cin>>u;
            if(ans[u] == 2) cout<<'?'; else cout<<ans[u];
        } else if(type == '+'){
            cin>>u>>v;
            graph[u].push_back({v, graph[v].size()});
            graph[v].push_back({u, graph[u].size()-1});
            visited[u] = q;
            if(group_id[u] == group_id[v] || ans[u] == 1 || ans[v] == 1) relax_dfs(u, graph, ans, group_id, q);
            else{
                if(ans[u] == 0){ans[u] = 2; ans[v] = 2; group_id[u] = group_id[v]; group_size[group_id[v]]++;}
                else if(ans[v] == 0){ans[u] = 2; ans[v] = 2; group_id[v] = group_id[u]; group_size[group_id[u]]++;}
                else if(group_size[group_id[u]] > group_size[group_id[v]]) merge(u, -1, graph, group_id); else merge(v, -1, graph, group_id);
            }
        } else if(type == '-'){
            cin>>u; ans[u] = 0;
            int prev = group_id[u];
            group_size[group_id[u]]--; group_id[u] = next_group_id; 
            group_size[group_id[u]]++; next_group_id++;

            if(group_size[prev] == 1) ans[graph[u][0].first] = 0;

            vector<int> neigh;
            for(int i=0; i<graph[u].size(); i++) neigh.push_back(graph[u][i].first);
            for(int i=0; i<graph[u].size(); i++) graph[graph[u][i].first][graph[u][i].second].first = -1;
            graph[u].clear();

            for(int i=0; i<(int)neigh.size()-1; i++){
                graph[neigh[i]].push_back({neigh[i+1], graph[neigh[i+1]].size()});
                graph[neigh[i+1]].push_back({neigh[i], graph[neigh[i]].size() - 1});
            }
        }
    }
    return 0;
}