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_max = 5 * 1e5+7;
int leader[n_max];
vector<int> zone;
vector<int> zone_status;
vector<int> zone_size;

int find_zone(int v){
    if(zone[v] != v){
        zone[v] = find_zone(zone[v]);
    }
    return zone[v];
}

int find(int v){
    return find_zone(leader[v]);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    int last = 0;
    zone.push_back(0);
    zone_status.push_back(0); // 0 - brak, 1 - nieznane, 2 - pewne
    zone_size.push_back(0);
    for(int i = 0; i < q; i++){
        char operation;
        cin >> operation;
        // Add new element
        if(operation == '+'){
            int a, b;
            cin >> a >> b;
            int zone_a = find(a);
            int zone_b = find(b);
            if(zone_status[zone_a] < zone_status[zone_b]){
                swap(a, b);
                swap(zone_a, zone_b);
            }
            // Zupelnie nowa przestzren
            if(zone_status[zone_a] == 0){
                last++;
                zone.push_back(last);
                zone_status.push_back(1);
                zone_size.push_back(2);
                leader[a] = last;
                leader[b] = last;
                if(a == b){
                    zone_status[last] = 2;
                }
                continue;
            }
            // Dodanie, ktore nic nie zmienia
            if(zone_status[zone_b] == 0){
                zone_size[zone_a]++;
                leader[b] = zone_a;
                continue;
            }
            // Jesli laczymy ta sama strefe
            if(zone_a == zone_b){
                zone_status[zone_a] = 2;
                continue;
            }
            zone[zone_b] = zone_a;
            zone_size[zone_a] += zone_size[zone_b];
        }  
        // Eliminate element
        if(operation == '-'){
            int a;
            cin >> a;
            int zone_a = find(a);
            zone_size[zone_a]--;
            if(zone_size[zone_a] == 1 and zone_status[zone_a] == 1){
                zone[zone_a] = 0;
            }
            leader[a] = 0;
        }
        // Question
        if(operation == '?'){
            int a;
            cin >> a;
            int zone_a = find(a);
            if(zone_status[zone_a] == 0){
                cout << 0;
            }
            if(zone_status[zone_a] == 1){
                cout << '?';
            }
            if(zone_status[zone_a] == 2){
                cout << 1;
            }
        }


    }



    return 0;
}