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
119
120
121
122
123
// Karol Kosinski 2024
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a),_b=(b);i<_b;++i)
#define FR_(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
#define FD_(i,b,a) for(int i=(b),_a=(a);i>=_a;--i)
#define ALL(c) (c).begin(),(c).end()
#define SIZE(c) int((c).size())
#define X first
#define Y second
#define endl '\n'
#define NAM(x) #x,'=',x
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
using TIII = tuple<int, int, int>;
template<class...T> void _cout(T...a){(cout<<...<<a);}

#ifndef ENABLE_DEBUG
#define DEB(k,p,f,x...)
#else
#define DEB(k,p,f,x...) {if(k)_cout("------",setw(4),__LINE__," : ",__FUNCTION__,endl);if(p)f(x);}
#endif
#define DEBF(f,x...)    DEB(1,1,f,x)
#define DEBL            DEBF(void,0)
#define DEBC(p,x...)    DEB(0,p,_cout,x)
#define DEBUG(x...)     DEBC(1,x)

constexpr int NX = 300'005;
constexpr int QX = 2'000'005;

struct FindUnion
{
    int P[QX], S[QX];

    void init(int n) { FOR(i,0,n) P[i] = i, S[i] = 1; }
    int find(int x) { return ( x == P[x] ) ? x : P[x] = find( P[x] ); }

    int unite(int x, int y)
    {
        x = find(x), y = find(y);
        if ( S[x] < S[y] ) swap(x, y);
        return S[x] += S[y], P[y] = x;
    }
};

FindUnion FU {};
int ID[NX], Si[QX];
char Vrf[QX];
int last_used;

void add()
{
    int a, b;
    cin >> a >> b;
    a = ID[a], b = ID[b];
    int fa = FU.find(a), fb = FU.find(b);
    if ( fa == fb )
    {
        Vrf[fa] = '1';
    }
    else
    {
        int f = FU.unite(fa, fb);
        Si[f] = Si[fa] + Si[fb];
        Vrf[f] = ( Vrf[fa] == '1' or Vrf[fb] == '1' ) ? '1' : '?';
    }
}

void remove()
{
    int c;
    cin >> c;
    int old_c = ID[c];
    int foc = FU.find(old_c);
    -- Si[foc];
    if ( Si[foc] == 1 )
    {
        if ( Vrf[foc] == '?' ) Vrf[foc] = '0';
    }
    int new_c = ++ last_used;
    int fnc = FU.find(new_c);
    Si[fnc] = 1;
    Vrf[fnc] = '0';
    ID[c] = new_c;
}

char question()
{
    int d;
    cin >> d;
    d = ID[d];
    return Vrf[ FU.find(d) ];
}

string testcase()
{
    string res, query;
    int n, q;
    cin >> n >> q;
    last_used = n;
    FU.init(QX);
    FR_(i,1,n) ID[i] = i, Si[i] = 1, Vrf[i] = '0';
    FOR(i,0,q)
    {
        cin >> query;
        switch ( query[0] )
        {
            case '+': add(); break;
            case '-': remove(); break;
            default : res.push_back( question() ); break;
        }
    }
    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << testcase() << endl;
    return 0;
}