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
#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
#include <unordered_set>
#include <memory>
#include <unistd.h>

using namespace std;


int main(){
    int n,q,a,b;
    char t;
    scanf("%d%d", &n, &q);

    shared_ptr<unordered_set<int>> nie = make_shared<unordered_set<int>>();
    shared_ptr<unordered_set<int>> tak = make_shared<unordered_set<int>>();
    vector<shared_ptr<unordered_set<int>>> v(n+1, nie);   
    for(int i=0; i < q; i++){
        scanf("\n%c", &t);
        if(t=='+'){
    
            scanf("%d%d", &a, &b);
            if(v[a] == nie){
                if(v[b]==nie){
                    if(a==b){
                        v[a]=tak;
                    }
                    else{
                        v[a] =make_shared<unordered_set<int>>(); //{a,b};
                        v[b] = v[a];
                        v[a]->insert(a);
                        v[b]->insert(b);
                    }
                }
                else if(v[b] == tak)
                    v[a] = tak;
                else{
                    v[a]=v[b];
                    v[a]->insert(a);
                }
            }
            else if(v[a] == tak){
                if(v[b]==nie)
                    v[b] = tak;
                else{
                    auto x = std::make_shared<unordered_set<int>>(*v[b]);
                        for(int i:*x)
                            v[i] = tak;    
                }
            }
            else{
                if(v[b] == nie){
                    v[b]=v[a];
                    v[b]->insert(b);
                }
                else if(v[b] ==tak){
                    auto x = std::make_shared<unordered_set<int>>(*v[a]);
                    for(int i: *x){
                        v[i] = tak;
                    }
                }
                else{
                    if (v[a]==v[b]){
                        auto x = std::make_shared<unordered_set<int>>(*v[a]);
                        
                        for(int i:*x){
                            v[i] = tak;

                        }
                    }
                    else if(v[a]->size() > v[b]->size()){
                        v[a]->merge(*v[b]);
                        for(auto i:*v[b])
                            v[i] = v[a];
                    }
                    else{
                        v[b]->merge(*v[a]);
                        for(auto i:*v[a])
                            v[i] = v[b];
                    }

                }

            }
            
        }
        
  
        else if(t=='-'){
            scanf("%d", &a);
            if(v[a] != tak){
                if(v[a]->size() == 2){
                    auto x = std::make_shared<unordered_set<int>>(*v[a]);
                    for(auto i:*x)
                        v[i] = nie;
                }
                else
                    v[a]->erase(a);
                    v[a] = nie;
            }
            else
                v[a] = nie;
        }
        else{
            scanf("%d", &a);
            if(v[a] == nie)
                printf("0");
            else if(v[a] == tak)
                printf("1");
            else
                printf("?"); 
        }

    }

}