思路：首先看到这题以为能用poj1904的模版直接A掉，WA了几次，然后又TLE了几次。还是想到了正解。
一开始我想的大致方向已经是对的了。先是由王子向每个喜欢的公主建边，再求一次最大匹配，找出匹配后，由匹配的公主向王子建边。
但可能会有没有匹配到的公主和王子，那么这个王子可以和任何它喜欢的公主结婚，这个公主也可以和任何喜欢她的王子结婚。
因为这些不在匹配中的点，加到匹配中后，减少的匹配数和增加的匹配数都是1。
我们也就想像poj1904那样，将他们变为一个强连通分量，我开始出错就在这。
直接在原图上将他们建边变为强连通分量会使原图性质发生改变。
所有我们对每个没有匹配的公主，建一个虚拟的王子，让他们变成匹配，然后由这个虚拟王子向每个公主建边。
对每个没有匹配的王子，建一个虚拟的公主，让他们变成匹配，然后每个王子向这个虚拟公主建边。
求一个Tarjan,判断是否为1个强连通分量即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define Maxn 2010
#define Maxm 400010
using namespace std;
int dfn[Maxn],low[Maxn],vi[Maxn],Stack[Maxn],head[Maxn],id[Maxn],n,e,lab,num,top,ans[Maxn];
int graphic[][],m,match[Maxn],cho[Maxn],mm;
struct Edge{
int u,v,next;
}edge[Maxm];
vector<int> q[Maxn],girl[Maxn];
void init()
{
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(vi,,sizeof(vi));
memset(head,-,sizeof(head));
memset(id,,sizeof(id));
memset(graphic,,sizeof(graphic));
memset(cho,,sizeof(cho));
memset(match,-,sizeof(match));
memset(ans,,sizeof(ans));
for(int i=;i<Maxn;i++)
q[i].clear(),girl[i].clear();
e=lab=num=top=mm=;
}
void add(int u,int v)
{
edge[e].u=u,edge[e].v=v,edge[e].next=head[u],head[u]=e++;
}
int dfs(int u)//匈牙利算法
{
int i;
for(i=;i<=m;i++)
{
if(!vi[i]&&graphic[u][i])
{
vi[i]=;
if(match[i]==-||dfs(match[i]))
{
match[i]=u;
return ;
}
}
}
return ;
}
int Tarjan(int u)
{
dfn[u]=low[u]=++lab;
vi[u]=;
Stack[top++]=u;
int i,j,v;
for(i=head[u];i!=-;i=edge[i].next)
{
v=edge[i].v;
if(!dfn[v])
{
Tarjan(v);
low[u]=min(low[u],low[v]);
}
if(vi[v])
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
++num;
do{
i=Stack[--top];
vi[i]=;
id[i]=num;
}while(i!=u);
}
return ;
}
void solve()
{
int i,j;
for(i=;i<=n+m+mm;i++)
if(!dfn[i])
Tarjan(i);
for(i=n+;i<=n+m;i++)
{
q[id[i]].push_back(i-n);
}
int cnt=;
for(i=;i<=n;i++)
{
int size=q[id[i]].size();
cnt=;
for(j=;j<size;j++)
{
if(graphic[i][q[id[i]][j]])
ans[cnt++]=q[id[i]][j];
}
printf("%d",cnt);
for(j=;j<cnt;j++)
printf(" %d",ans[j]);
printf("\n");
}
}
int main()
{
int a,b,i,j,t,Case=;
scanf("%d",&t);
while(t--)
{
init();
scanf("%d%d",&n,&m);
for(i=;i<=n;i++)
{
scanf("%d",&a);
while(a--)
{
scanf("%d",&b);
add(i,b+n);
graphic[i][b]=;
}
}
int num=;
memset(match,-,sizeof(match));
for(i=;i<=n;i++)
{
memset(vi,,sizeof(vi));
if(dfs(i))
num++;
}
mm=;
for(i=;i<=m;i++)
{
if(match[i]==-)
{
mm++;
add(n+m+mm,i+n);
add(i+n,n+m+mm);
for(j=;j<=m;j++)
add(n+m+mm,j+n);
}
else
{
cho[match[i]]=;
}
add(i+n,match[i]);
}
for(i=;i<=n;i++)
{
if(cho[i]==)
{
mm++;
add(i,n+m+mm);
add(n+m+mm,i);
for(j=;j<=n;j++)
add(j,n+m+mm);
}
}
memset(vi,,sizeof(vi));
printf("Case #%d:\n",++Case);
solve();
}
return ;
}