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
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
// #define int ll
// #define N 
using namespace std;
const int N=1500005;
int n,q,fa[N],id[N],vis[N],tot[N];
poly s[N];
inline int gf(int x)
{
    while (x!=fa[x]) x=fa[x]=fa[fa[x]];
    return x;
}
void BellaKira()
{
    cin>>n>>q;
    for (int i=1;i<=n;i++) fa[i]=i,tot[i]=1,id[i]=i,s[i].push_back(i);
    while (q--)
    {
        char c;
        cin>>c;
        if (c=='?')
        {
            int x;
            cin>>x;
            if (vis[x]) cout<<'1';
            else 
            if (tot[gf(id[x])]==1) cout<<'0';
            else cout<<'?';
        } else
        if (c=='-')
        {
            int x;
            cin>>x;
            if (vis[x]==0) tot[gf(id[x])]--;

            vis[x]=0;
            id[x]=++n;
            fa[id[x]]=id[x];

            tot[id[x]]=1;
            s[id[x]].push_back(x);
        } else
        {
            int x,y;
            cin>>x>>y;
            int xx=gf(id[x]),yy=gf(id[y]);
            if (xx==yy)
            {
                for (auto u:s[xx])  if (gf(id[u])==xx) vis[u]=1;
                poly().swap(s[xx]);
                tot[xx]=0;
            } else
            {
                if (vis[x]||vis[y])
                {
                    if (vis[y]) swap(x,y),swap(xx,yy);
                    for (auto u:s[yy])  if (gf(id[u])==yy) vis[u]=1;
                    fa[yy]=xx;
                    vis[x]=vis[y]=1;
                }
                else
                {
                    fa[xx]=yy;
                    vis[x]=vis[y]=0;
                    if (s[xx].size()>s[yy].size()) s[xx].swap(s[yy]);
                    for (auto u:s[xx]) s[yy].push_back(u);
                    tot[yy]+=tot[xx];
                }
            }
        }
    }

                    

            
}
signed main()
{
    IOS;
    cin.tie(0);
    int T=1;
    while (T--)
    {
        BellaKira();
    }
}
/*list:
1.mod 998244353 or 1e9+7 or ???
2.N
3.duipai shuju xingtai duoyidian
...
*/