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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll inf=1e18;

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    ll n,q;cin>>n>>q;
    vector<ll>state(n),uf(n),act(n),sz(n);
    vector<list<ll>>stl(n);
    for(int i=0;i<n;i++)
    {
        uf[i]=i;act[i]=0;sz[i]=1;
        stl[i].push_back(i);
    }
    auto fi=[&](auto fi,int i)->int
    {
        if(i==uf[i])return i;
        else return uf[i]=fi(fi,uf[i]);
    };
    auto un=[&](int i,int j)->int
    {
        if(state[i]==1)
        {
            state[j]=1;
            return 0;
        }
        if(state[j]==1)
        {
            state[i]=1;
            return 0;
        }
        i=fi(fi,i);j=fi(fi,j);
        if(i!=j)
        {
            if(stl[i].size()<stl[j].size())swap(i,j);
            uf[j]=i;
            act[i]+=act[j]+1;
            sz[i]+=sz[j];
            stl[i].splice(stl[i].end(),stl[j]);
            return i;
        }
        else return -i-1;
    };
    while(q--)
    {
        char ch;cin>>ch;
        if(ch=='+')
        {
            int a,b;cin>>a>>b;
            a--;b--;state[a]=state[b]=2;
            int res=un(a,b);
            if(res<0)
            {
                int c=-res-1;
                list<ll>ve=move(stl[c]);
                for(ll a:ve)
                {
                    if(state[a]==2)
                    {
                        state[a]=1;
                    }
                    stl[a]=list<ll>{a};
                    sz[a]=1;
                    uf[a]=a;
                    act[a]=0;
                }
            }
        }
        else if(ch=='-')
        {
            int c;cin>>c;
            c--;state[c]=0;
            c=fi(fi,c);
            act[c]--;sz[c]--;
            if(sz[c]==1)
            {
                list<ll>ve=move(stl[c]);
                for(ll a:ve)
                {
                    if(state[a]==2)
                    {
                        state[a]=0;
                    }
                    stl[a]=list<ll>{a};
                    sz[a]=1;
                    uf[a]=a;
                    act[a]=0;
                }
            }
        }
        else
        {
            ll i;cin>>i;i--;
            if(state[i]==2)cout<<"?";
            else cout<<state[i];
        }
    }
}