Eva

Time Limit: 20 Sec  Memory Limit: 256 MB

Description

四年一度的幻想乡大选开始了，最近幻想乡最大的问题是很多来历不明的妖

怪涌入了幻想乡，扰乱了幻想乡昔日的秩序。但是幻想乡的建制派妖怪（人类）

博丽灵梦和八云紫等人整日高谈所有妖怪平等，幻想乡多元化等等，对于幻想乡

目前面临的种种大问题却给不出合适的解决方案。

风间幽香是幻想乡里少有的意识到了问题的严重性的大妖怪。她这次勇敢的

站了出来参加幻想乡大选。提出包括在幻想乡边境建墙（并让人类出钱），大力

开展基础设施建设挽回失业率等一系列方案，成为了大选年出人意料的黑马并顺

利的当上了幻想乡的大统领。

幽香上台以后，第一项措施就是要修建幻想乡的公路。幻想乡有 N 个城市，

之间原来没有任何路。幽香向选民承诺要减税，所以她打算只修 N- 1 条路将

这些城市连接起来。但是幻想乡有正好 N- 1 个建筑公司，每个建筑公司都想

在修路的过程中获得一些好处。

虽然这些建筑公司在选举前没有给幽香钱，幽香还是打算和他们搞好关系，

因为她还指望他们帮她建墙。所以她打算让每个建筑公司都负责一条路来修。

每个建筑公司都告诉了幽香自己有能力负责修建的路是哪些城市之间的。所

以幽香打算选择 N-1 条能够连接幻想乡所有城市的边，然后每条边都交给一

个能够负责该边的建筑公司修建，并且每个建筑公司都恰好修一条边。

幽香现在想要知道一共有多少种可能的方案呢？两个方案不同当且仅当它

们要么修的边的集合不同，要么边的分配方式不同。

Input 

第一行包含一个正整数 N(N<=17)， 表示城市个数。

接下来 N-1 行，其中第 i行表示第 i个建筑公司可以修建的路的列表：

以一个非负数mi 开头，表示其可以修建 mi 条路，接下来有mi 对数，

每对数表示一条边的两个端点。其中不会出现重复的边，也不会出现自环。

Output 

仅一行一个整数，表示所有可能的方案数对 10^9 + 7 取模的结果。

Sample Input

4
2 3 2 4 2
5 2 1 3 1 3 2 4 1 4 3
4 2 1 3 2 4 1 4 2

Sample Output

17

/**************************************************************

    Problem: 4596

    User: ictsing

    Language: C++

    Result: Accepted

    Time:9356 ms

    Memory:1368 kb

****************************************************************/

 

/**************************************************************

    Problem: 4596

    User: mywaythere

    Language: C++

    Result: Accepted

    Time:9336 ms

    Memory:1368 kb

****************************************************************/

  

//给定n个点，要求连n-1条边

//N-1个公司，每个公司可以修某些路

//问如何安排使每个公司恰修一条路

//从每个集合中选一个数，每个集合必选

/*

很容易想到matix-tree，

但是这道题肯定不止matrix-trtree，

计数问题要想到容斥，

每个集合选一个数的方案=2^n-sigma（i）{一定不修}+sigma（i，j)+...

通过状态数进行容斥

*/

#include<cstring>

#include<iostream>

#include<cstdio>

using namespace std;

const int mm = 17+4;

typedef long long ll;

ll a[mm][mm];

ll ans=0;

int v1[mm][mm*mm],v2[mm][mm*mm];

const int mod = 1000000007 ;

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

       num=num*10+ch-'0';

       ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

int num[mm];

ll matrixtree(int n)

{

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

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

          a[i][j]=(a[i][j]+mod)%mod;

    ll ret=1;

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

    {

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

        {

            ll aa=a[i][i],bb=a[j][i];

            while(bb)

            {

                ll tmp=aa/bb;aa%=bb,swap(aa,bb);

                for(int k=i;k<n;k++) a[i][k]=(a[i][k]-a[j][k]*tmp+mod)%mod;

                for(int k=i;k<n;k++) swap(a[i][k],a[j][k]);

                ret=-ret;

            }

        }

        if(!a[i][i]) return 0;

        ret=ret*a[i][i]%mod;

    }

    return (ret+mod)%mod;

}

int main()

{

    int n=read();

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

    {

       num[i]=read();

       for(int j=1;j<=num[i];j++)

       v1[i][j]=read(),v2[i][j]=read();

    }

    int mmt=1<<(n-1);

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

    {

        int x=0;

        memset(a,0,sizeof(a));

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

        {

            if(i&(1<<(j-1)))

            {

                x++;

                for(int k=1;k<=num[j];k++)

                {

                    a[v1[j][k]][v2[j][k]]--;

                    a[v2[j][k]][v1[j][k]]--;

                    a[v1[j][k]][v1[j][k]]++;

                    a[v2[j][k]][v2[j][k]]++;

                }

            }

        }

        if((n-x)&1) ans=(ans+matrixtree(n)+mod)%mod;

        else ans=(ans-matrixtree(n)+mod)%mod;

    }

    printf("%lld\n",(ans+mod)%mod);

    return 0;

}