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

using namespace std;

const int N = 300 * 1000 + 1;
const int M = 5 * 1000 * 1000 + 1;

vector<int> groups[M];

pair<int,int> where[N];
int type[N];
int free_slot;

void remove(int a) {
    int last = groups[where[a].first].size() - 1;
    where[groups[where[a].first][last]] = {where[a].first, where[a].second};
    swap(groups[where[a].first][where[a].second], groups[where[a].first][last]);
    //cout << "remove " << a << "\n";
    //for (auto el : groups[where[a].first])
    //    cout << el << " ";
    //cout << "\n";
    groups[where[a].first].pop_back();
    if (groups[where[a].first].size() == 1)
        type[groups[where[a].first][0]] = 0;
    
    type[a] = 0;
    groups[free_slot++].push_back(a);
    where[a] = {free_slot - 1, 0};
}

void dissolve(int a) {
    int prev = where[a].first;
    //cout << "dissolve" << " " << a << "\n"; 
    for (auto el : groups[where[a].first]) {
    //    cout << el << " ";
        groups[free_slot++].push_back(el);
        where[el] = {free_slot - 1, 0};
        type[el] = 1;
    }
    //cout << "\n";
    groups[prev].clear();
}

void join(int a, int b) {
    if (groups[where[a].first].size() > groups[where[b].first].size())
        swap(a, b);
    
    if (groups[where[b].first].size() == 1)
        type[b] = 2;
    
    int prev = where[a].first;
    for (auto el : groups[where[a].first]) {
        groups[where[b].first].push_back(el);
        where[el] = {where[b].first, (int)groups[where[b].first].size() - 1};
        type[el] = 2;
    }
    groups[prev].clear();
}

int main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);    
    
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        groups[i - 1].push_back(i);
        where[i] = {i - 1, 0};
        type[i] = 0; 
    }
    free_slot = n;
    
    int a, b;
    string query_type;
    for (int i = 0; i < q; i++) {
        cin >> query_type;
        if (query_type == "-") {
            cin >> a;
            remove(a);
        }
        else if (query_type == "+" ) {
            cin >> a >> b;
            if (type[a] == 1) 
                dissolve(b);
            else if (type[b] == 1)
                dissolve(a);
            else if (where[a].first == where[b].first) 
                dissolve(a);
            else
                join(a, b);
        }
        else if (query_type == "?") {
            cin >> a;
            if (type[a] == 0)
                cout << '0';
            else if (type[a] == 1)
                cout << '1';
            else
                cout << '?';
        }
    }
    cout << "\n";
    return 0;
}