#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>q1,q2; //printf("nxt[%d]=%d\n",x,nxt[m_p(x,-1)]); //printf("nxt[%d]=%d\n",y,nxt[m_p(y,-1)]); set<pi>S1,S2; set<int>nd1,nd2; if(nxt[m_p(x,-1)]<int(v[x].size()))q1.push(m_p(x,nxt[m_p(x,-1)])),S1.insert(m_p(x,nxt[m_p(x,-1)])); if(nxt[m_p(y,-1)]<int(v[y].size()))q2.push(m_p(y,nxt[m_p(y,-1)])),S2.insert(m_p(y,nxt[m_p(y,-1)])); while(q1.size()&&q2.size()){ auto it1=q1.front(),it2=q2.front();q1.pop(),q2.pop(); auto expand=[](int x,int y){ int ty=y; y=nxt[m_p(x,y)]; if(y<v[x].size())return m_p(x,y); y=v[x][ty].p1; return m_p(y,nxt[m_p(y,-1)]); }; auto f1=expand(it1.p1,it1.p2),f2=expand(it2.p1,it2.p2); if(!S1.count(f1))S1.insert(f1),q1.push(f1); if(!S2.count(f2))S2.insert(f1),q2.push(f2); } if(q1.empty()){++belct; bel[x]=belct; for(auto it:S1){ bel[it.p1]=belct; bel[v[it.p1][it.p2].p1]=belct; } }else {++belct; bel[y]=belct; for(auto it:S2){ //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; 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; }