我不好说，因为考场上我想成二分图然后就gg了

这题不难，真的不难。

$|T_i|\le 2$这个性质一看就非常亲切啊，可以看成一条$a_i$到$b_i$的连边，不妨将问题做一些泛化，将$|T_i|=1$看成连向$a_i$的自环。

那么对于一个连通块显然边的数目不超过点的数目，让我们先讨论一些比较简单的情形。

如果基环树且基环为自环，那么选择方式唯一，简单算一下即可。

如果基环树且基环不为自环，那么基环外选择方式唯一，基环内有两种方式，简单贪心一下应该不难得出答案。

如果为树，假设{ai}\{a_i\}{ai​}已经确定了，不妨看成是以$u$为根并且完成定向的一颗有根树，$\text{Bob}$可以将$v$到根节点的路径上的边反向，那么相当于每个点存了一个答案，初始所有点答案都为$0$，$\text{Bob}$会选择答案最小的那个点。然后$\text{Alice}$依次加入每条边，对于没有别固定的边$(u,v)$，设$u$是$v$的父亲，如果选$v$相当于$v$子树外的点答案$+1$，如果选$u$相当于$v$子树内的点答案$+1$（称为不动点），如果有两个点$u,v$都是翻转点，那么显然$u,v$满足祖先关系（否则不优），而显然选深度小的点作为不动点更优，那么就做完了。

复杂度$O(n\log n)$。

总之是非常套路的题，但是不知道为啥考场上没想出来。

总之就是非常难写，今年省选代码量确实有一点点大

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define db double
#define fi first
#define se second
using namespace std;
const int N=1e6+5;
int T,n,m,fa[N],sz1[N],sz2[N],a[N][2],b[N][2];
int rt,re,pre[N],prepos[N],visit[N],task,res,dfn[N],num,home[N],cntnode;
int head[N*2],nxt[N*2],to[N*2],pos[N*2],tot;
int posedge;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
struct node{int dat,min;
}t[N<<2];
void Add(int p,int x){t[p].min+=x,t[p].dat+=x;
}
void pushup(int p){t[p].min=min(t[p<<1].min,t[p<<1|1].min);
}
void pushdown(int p){if(t[p].dat){Add(p<<1,t[p].dat),Add(p<<1|1,t[p].dat);t[p].dat=0;}
}
void upd(int p,int l,int r,int ql,int qr,int x){if(ql<=l&&r<=qr){Add(p,x);return;}int mid=l+r>>1;pushdown(p);if(ql<=mid)upd(p<<1,l,mid,ql,qr,x);if(mid<qr)upd(p<<1|1,mid+1,r,ql,qr,x);pushup(p);
}
int qry(int p,int l,int r,int ql,int qr){if(ql<=l&&r<=qr)return t[p].min;int mid=l+r>>1;pushdown(p);if(qr<=mid)return qry(p<<1,l,mid,ql,qr);if(mid<ql)return qry(p<<1|1,mid+1,r,ql,qr);return min(qry(p<<1,l,mid,ql,qr),qry(p<<1|1,mid+1,r,ql,qr));
}
void add(int x,int y,int z){to[++tot]=y,pos[tot]=z,nxt[tot]=head[x],head[x]=tot;to[++tot]=x,pos[tot]=z,nxt[tot]=head[y],head[y]=tot;
}
void unionset(int x,int y){int u=find(x),v=find(y);if(u!=v)fa[u]=v,sz1[v]+=sz1[u]+1,sz2[v]+=sz2[u];else sz1[v]++;
}
int calc(int pos,int v){assert(v);return a[pos][0]==v||a[pos][1]==v;
}
int X,Y,Z;
int check(int pos){return a[pos][0]==b[pos][0]&&a[pos][1]==b[pos][1]||a[pos][0]==b[pos][1]&&a[pos][1]==b[pos][0];
}
//fixed
void findroot(int u,int topf){visit[u]=task;for(int k=head[u];k;k=nxt[k]){if(k!=(topf^1)){int v=to[k];if(visit[v]!=task)findroot(v,k);else {rt=u;if(u==v)posedge=pos[k];}}}
}
//fixed
void dfs(int u,int topf){visit[u]=task;for(int k=head[u];k;k=nxt[k]){int v=to[k];if(k!=(topf^1)){if(visit[v]!=task){pre[v]=u,prepos[v]=pos[k],dfs(v,k);res+=calc(pos[k],v);}else if(u!=rt){assert(!re);re=u;if(check(pos[k])){Z++;}else {if(calc(pos[k],rt))X++;else if(calc(pos[k],re))Y++;}}}}
}
int solve1(int u){rt=u,re=0,task++;X=0,Y=0,Z=0,res=0,posedge=0;findroot(rt,0);if(posedge)res+=calc(posedge,rt);task++;dfs(rt,0);if(!re)return res;assert(rt!=re);while(re!=rt){int tmp=prepos[re];res-=calc(tmp,re);if(check(tmp)){Z++;}else{if(calc(tmp,re))X++;else if(calc(tmp,pre[re]))Y++;}re=pre[re];}if(X>Y)swap(X,Y);if(X+Z<=Y)return X+Z+res;return (X+Y+Z)/2+res;
}
void modify(int u,int state,int f){if(state==0){upd(1,1,m,dfn[u],dfn[u]+home[u]-1,f);}else{upd(1,1,m,dfn[u],dfn[u]+home[u]-1,-f);upd(1,1,m,1,cntnode,f);}
}
void dfs1(int u,int topf){dfn[u]=++num,home[u]=1,cntnode++;for(int k=head[u];k;k=nxt[k]){int v=to[k];if(v!=topf){dfs1(v,u),home[u]+=home[v];}}
}
void dfs2(int u,int topf,int f){for(int k=head[u];k;k=nxt[k]){int v=to[k];if(v!=topf){if(check(pos[k])){modify(v,1,f);}else if(calc(pos[k],v)){modify(v,1,f);}else if(calc(pos[k],u)){modify(v,0,f);}dfs2(v,u,f);}}
}
void dfs3(int u,int topf){res=max(res,qry(1,1,m,1,cntnode));for(int k=head[u];k;k=nxt[k]){int v=to[k];if(v!=topf){if(check(pos[k])){modify(v,1,-1);modify(v,0,1);}dfs3(v,u);if(check(pos[k])){modify(v,1,1);modify(v,0,-1);}}}
}
int solve2(int u){num=0,cntnode=0,dfs1(u,0);assert(cntnode==sz2[find(u)]);res=0;dfs2(u,0,1),dfs3(u,0),dfs2(u,0,-1);assert(t[1].min==0);return res;
}
int solve(){int tot=0;for(int i=1;i<=m;i++){if(find(i)==i){if(sz1[i]>sz2[i]){return -1;}if(sz1[i]==sz2[i])tot+=solve1(i);else tot+=solve2(i);}}return tot;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>T;while(T--){cin>>n>>m;tot=1;for(int i=1;i<=m;i++)head[i]=0;for(int i=1;i<=m;i++)fa[i]=i,sz1[i]=0,sz2[i]=1;for(int i=1;i<=n;i++)a[i][0]=a[i][1]=b[i][0]=b[i][1]=0;for(int i=1;i<=n;i++){int k;cin>>k;while(k--)cin>>a[i][k];}for(int i=1;i<=n;i++){int k;cin>>k;if(k==2){while(k--)cin>>b[i][k];unionset(b[i][0],b[i][1]);add(b[i][0],b[i][1],i);}else{while(k--)cin>>b[i][k];unionset(b[i][0],b[i][0]);add(b[i][0],b[i][0],i);}}cout<<solve()<<"\n";}
}