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
// #include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
struct tree {
    unordered_set<int> elems;
    int power;
};


vector<tree*> trees;


void mark(int arg0,int arg1) {
    tree* ti = trees[arg0];
    tree* tj = trees[arg1];

    if (ti != NULL && tj != NULL) {
        if (ti == tj) {
            ti->power++;
        } else {
            if (tj->elems.size()>ti->elems.size()) {
                tj, ti = ti, tj;
            }
            ti->power = ti->power + tj->power +1;
            for (auto v : tj->elems) {
                trees[v] = ti;
                ti->elems.insert(v) ;
            }
        }
    } else if(ti != NULL){
        ti->elems.insert(arg1);
        ti->power++;
        trees[arg1] = trees[arg0];
    } else if(tj != NULL){
        tj->elems.insert(arg0);
        tj->power++;
        trees[arg0] =  trees[arg1];
    }else {
        ti = new(tree);
        ti->elems.insert(arg0);
        ti->elems.insert(arg1);
        ti->power=1;
        trees[arg0] = ti;
        trees[arg1] = ti;
    }

    // cout <<endl <<"ALTER DEBUG: " <<i << ":"<< j<< endl << flush;
    // tree_dbg();
}



int main()
{
    FAST
    int n, q;
    cin >> n >> q;
    trees = vector<tree*>(n+1);
    char op;
    int arg0, arg1;
    tree *ti;
    tree *tj;
    int tp;
    for (int i = 0; i < q; i++)
    {
        cin >> op;
        switch (op)
        {
        case '+':
            cin >> arg0 >> arg1;
            mark(arg0,arg1);
            break;
        case '-':
            cin >> arg0;
            ti = trees[arg0];
            ti->elems.erase(arg0);
            ti->power--;
            trees[arg0] = NULL;
            break;
        case '?':
            cin >> arg0;
            ti = trees[arg0];
            if (ti == NULL || ti->power == 0) {
                cout << 0;
            } else if (ti->elems.size() == ti->power) {
                cout << 1;
            } else {
                cout << "?";
            }
            break;
        default:
            break;
        }
    }
}