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

using namespace std;

struct event{char x; int a, b;};

int f(int i, vector<int> &P)
{
    if(P[i] == i) return i;
    return P[i] = f(P[i], P);
}

void u(int a, int b, vector<int> &P, vector<queue<int>> &C, vector<int> &S)
{
    if(C[a].front() < C[b].front()) swap(a, b);
    if(C[a].front() == C[b].front() && S[a] < S[b]) swap(a, b);

    S[P[a]] += S[P[b]];
    P[P[b]] = P[a];
}

void query(event e, vector<queue<int>> &C, vector<int> &R, vector<int> &P, vector<int> &S)
{
    if(e.x == '+')
    {
        int v = f(e.a, P);
        int w = f(e.b, P);
        if(w == v) R[v] = 1;
        else if(R[w] == 1 || R[v] == 1) R[v] = R[w] = 1;
        else u(v, w, P, C, S);
        
        if(R[P[P[e.a]]] == 0) R[P[P[e.a]]] = 2;
    }
    
    else if(e.x == '-')
    {
        R[e.a] = 0;
        int v = f(e.a, P);
        P[e.a] = e.a;
        S[v]--;
        S[e.a] = 1;
        C[e.a].pop();
    }
    
    else 
    {
        int v = f(e.a, P);
        if(R[v] == 2 && S[v]>1) cout << "?";
        else if(R[v] == 2) cout << 0;
        else cout << R[v];
    }

    /*cerr << "\n";
    for(auto it:P) cerr << it << " ";
    cerr << S[6];
    cerr << "\n";*/
}

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

    int n, q;
    cin >> n >> q;
    vector<queue<int>> C(n);
    vector<event> E;
    for(int i=0; i<q; i++)
    {
        char x;
        int a, b = 0;
        cin >> x >> a;
        if(x == '+') cin >> b;
        a--;
        b--;
        E.push_back({x, a, b});
        if(x == '-') C[a].push(i);
    }
    for(int i=0; i<n; i++) C[i].push(q);

    vector<int> P(n), S(n, 1), R(n);
    for(int i=0; i<n; i++) P[i] = i;
    for(auto it:E) query(it, C, R, P, S);

    cout << "\n";
}