#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define p_b push_back #define m_p make_pair using namespace std; typedef long long ll; const int maxn=1e6+10,mod=1e9+7; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } inline char gc(){ char ch=getchar(); while(ch!='-'&&ch!='?')ch=getchar(); return ch; } int n,m,res,ndct,bel[maxn],vis[maxn],hd[maxn],belct; struct Dsu { int fa[maxn]; int fd(int u){ if(u==fa[u])return u; return fa[u]=fd(fa[u]); } void init(int n){ up(i,1,n)fa[i]=i; } }dsu; vector<pi>v[maxn]; map<pi,int>pos; map<pi,int>ID; map<pi,int>nxt,pre; struct nd { int x,y,bel,del; }d[maxn<<1]; void fc(){ up(i,1,n)up(j,0,int(v[i].size())-1)pos[m_p(i,v[i][j].p1)]=j; for(int i=2;i<=2*m+1;i++)if(!d[i].bel){ d[i].bel=++ndct; int u=d[i].y,lst=d[i].x; int cc=0; while(u!=d[i].x){ int p=pos[m_p(u,lst)]; auto it=((p==v[u].size()-1)?v[u][0]:v[u][p+1]); d[it.p2].bel=ndct; lst=u,u=it.p1; } }dsu.init(ndct); } void del(int x,int y){ int p=pos[m_p(x,y)]; nxt[m_p(x,pre[m_p(x,p)])]=nxt[m_p(x,p)]; pre[m_p(x,nxt[m_p(x,p)])]=pre[m_p(x,p)]; p=pos[m_p(y,x)]; nxt[m_p(y,pre[m_p(y,p)])]=nxt[m_p(y,p)]; pre[m_p(y,nxt[m_p(y,p)])]=pre[m_p(y,p)]; } void sp(int x,int y){ //cout<<"sp "<<x<<" "<<y<<endl; queue<pi>q[3]; //printf("nxt[%d]=%d\n",x,nxt[m_p(x,-1)]); //printf("nxt[%d]=%d\n",y,nxt[m_p(y,-1)]); set<pi>S[3]; if(nxt[m_p(x,-1)]<int(v[x].size()))q[1].push(m_p(x,nxt[m_p(x,-1)])),S[1].insert(m_p(x,nxt[m_p(x,-1)])); if(nxt[m_p(y,-1)]<int(v[y].size()))q[2].push(m_p(y,nxt[m_p(y,-1)])),S[2].insert(m_p(y,nxt[m_p(y,-1)])); while(q[1].size()&&q[2].size()){ up(i,1,2){ auto it=q[i].front();q[i].pop(); int x=it.p1,y=it.p2; int id=v[x][y].p1; if(nxt[m_p(id,-1)]<int(v[id].size())){ auto w=m_p(id,nxt[m_p(id,-1)]); if(!S[i].count(w))S[i].insert(w),q[i].push(w); } if(nxt[m_p(x,y)]<int(v[x].size())){ auto w=m_p(x,nxt[m_p(x,y)]); if(!S[i].count(w))S[i].insert(w),q[i].push(w); } } } if(q[1].empty()){++belct; bel[x]=belct; for(auto it:S[1]){ bel[it.p1]=belct; bel[v[it.p1][it.p2].p1]=belct; } }else {++belct; bel[y]=belct; for(auto it:S[2]){ //cout<<"! "<<it.p1<<" "<<v[it.p1][it.p2].p1<<endl; bel[it.p1]=belct; bel[v[it.p1][it.p2].p1]=belct; } } } void slv(){ n=read();int q=read(); up(i,1,n){ int k=read(); while(k--){ int x=read(); if(ID.count(m_p(i,x))){ v[i].p_b(m_p(x,ID[m_p(i,x)])); continue; } ++m; d[m*2].x=i,d[m*2].y=x;ID[m_p(i,x)]=m*2; d[m*2+1].x=x,d[m*2+1].y=i;ID[m_p(x,i)]=m*2+1; v[i].p_b(m_p(x,ID[m_p(i,x)])); } }up(i,1,n){ int sz=v[i].size(); up(j,-1,sz-1)nxt[m_p(i,j)]=j+1,pre[m_p(i,j+1)]=j; } fc(); int res=1,lst=0; while(q--){ char op=gc(); int x=read()^lst,y=read()^lst; //int x=read(),y=read(); if(op=='?'){ lst=(bel[x]==bel[y]); printf("%d\n",lst); continue; } int id=ID[m_p(x,y)]; int a=d[id].bel,b=d[id^1].bel;del(x,y); if(dsu.fd(a)==dsu.fd(b))res++,sp(x,y); dsu.fa[dsu.fd(a)]=dsu.fd(b); lst=res;printf("%d\n",res); //up(i,1,n)printf("%d ",bel[i]);printf("\n"); } } int main(){ //freopen("planar.in","r",stdin); //freopen("planar.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }