意甲冠军：今天，有n王子，m公主。现在给他们配对，与王子会嫁给一个男人，他喜欢。公主无法做出选择。

这标题去咬硬，还有一类似的题目poj1904。那个题目也是给王子与公主配对，但那个是王子公主各n个，且给定了一个完美匹配，然后求每一个王子能够做出的选择且不影响最大匹配数目。那题是先建各条喜欢关系的边。然后在由被选择的公主连一条边到与之配对的王子。强连通之后假设一个王子和一个公主在一个强连通分量中，那么他们结合的话，他们的还有一半也各自能在强连通中找到另外的匹配，就是符合题意的结果了。

这个题目算是升级版把。我们须要做的先是用匈牙利算法求出最大匹配res，然后建立m-res个虚拟王子与m-res单身公主准备匹配，建立n-res个虚拟公主与n-res个单身王子准备匹配。过程就是虚拟王子要喜欢每个公主，相同虚拟公主也要被每个王子喜欢，这样最大匹配一定是n+m-res.求出一个这种完美匹配，然后再套用poj1904的思路用强连通做。建议先做下1904额。

代码：

#include<iostream>

#include<cstdio>

#include<string>

#include<cmath>

#include<queue>

#include<stack>

#include<map>

#include<cstring>

#include<algorithm>

#define rep(i,a,b) for(int i=(a);i<(b);i++)

#define rev(i,a,b) for(int i=(a);i>=(b);i--)

#define clr(a,x) memset(a,x,sizeof a)

#define inf 0x3f3f3f3f

typedef long long LL;

using namespace std;

const int eps=0.00000001;

const int maxn=2005;

const int maxm=maxn*maxn/2;

int first[maxn],link[maxn];

int nex[maxm],w[maxm],v[maxm],u[maxm];

bool done[maxn],g[maxn][maxn];

int n,m,ecnt;

void add_(int a,int b,int c=0)

{

    u[ecnt]=a;

    v[ecnt]=b;

    w[ecnt]=c;

    nex[ecnt]=first[a];

    first[a]=ecnt++;

}

bool dfs(int s)

{

    for(int e=first[s];~e;e=nex[e])

    if(!done[v[e]])

    {

        done[v[e]]=true;

        if(link[v[e]]==-1||dfs(link[v[e]]))

        {

            link[v[e]]=s;

            return true;

        }

    }

    return 0;

}

int hungary(int n)

{

    int ans=0;

    clr(link,-1);

    for(int i=1;i<=n;i++)

    {

        clr(done,false);

        if(dfs(i))ans++;

    }

    return ans;

}

int low[maxn],dfn[maxn],stck[maxn],belong[maxn];

int index,top,scc;

bool ins[maxn];

int num[maxn];

int in[maxn],out[maxn];

void tarjan(int u)

{

    low[u]=dfn[u]=++index;

    stck[top++]=u;

    ins[u]=1;

    for(int e=first[u];~e;e=nex[e])

    {

        if(!dfn[v[e]])

        {

            tarjan(v[e]);

            low[u]=min(low[u],low[v[e]]);

        }

        else if(ins[v[e]])low[u]=min(low[u],dfn[v[e]]);

    }

    if(low[u]==dfn[u])

    {

        int v;

        scc++;

        do

        {

            v=stck[--top];

            ins[v]=false;

            belong[v]=scc;

            num[scc]++;

        }while(v!=u);

    }

}

void solve(int n)

{

    clr(dfn,0);

    clr(ins,0);

    clr(num,0);

    index=scc=top=0;

    for(int i=1;i<=n;i++)

        if(!dfn[i])tarjan(i);

}

int main()

{

    int t,a,b,c,k,cas=1,key=1000;

    scanf("%d",&t);

    while(t--)

    {

        clr(first,-1);ecnt=0;

        clr(g,false);

        scanf("%d%d",&n,&m);

        for(int i=1;i<=n;i++)

        {

            scanf("%d",&k);

            while(k--)

            {

                scanf("%d",&a);

                if(!g[i][a])

                {

                    g[i][a]=1;

                    add_(i,a+key);

                }

            }

        }

        int res=hungary(n);

        int nn=n+m-res;

        for(int i=n+1;i<=nn;i++)

            for(int j=1;j<=nn;j++)

            add_(i,j+key),g[i][j]=1;

        for(int i=1;i<=n;i++)

            for(int j=m+1;j<=nn;j++)

            add_(i,j+key),g[i][j]=1;

        hungary(nn);

        ecnt=0;clr(first,-1);

        for(int i=1;i<=nn;i++)

            if(link[i+key]!=-1)add_(i+nn,link[i+key]);

        for(int i=1;i<=nn;i++)

            for(int j=1;j<=nn;j++)

            if(g[i][j])add_(i,j+nn);

        solve(2*nn);

        printf("Case #%d:\n",cas++);

        int ans[1000];

        for(int i=1;i<=n;i++)

        {

            int en=0;

            for(int j=1;j<=m;j++)

                if(g[i][j]&&belong[j+nn]==belong[i])ans[en++]=j;

            printf("%d",en);

            for(int i=0;i<en;i++)

                printf(" %d",ans[i]);

            puts("");

        }

    }

    return 0;

}