分析
这很明显是矩阵树定理，但是每个建筑公司都恰好修建一条边非常难做，
考虑如果一个建筑公司在某个方案中并没有恰好修建一条边，
那么这种方案一定能在不选其它任意一个公司的方案中被减掉，
那就可以用容斥定理做，枚举选择公司的二进制状态，求出基尔霍夫矩阵
代码
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define rr register
using namespace std;
const int mod=1000000007;
int a[18][18],Aa[17][18][18],xo[65536],n,ans,all;
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline signed ksm(int x,int y){
rr int ans=1;
for (;y;y>>=1,x=1ll*x*x%mod)
if (y&1) ans=1ll*ans*x%mod;
return ans;
}
inline void MO(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
inline void Mo(int &x,int y){x=x<y?x-y+mod:x-y;}
inline signed Gauss(int n){
rr int ans=1;
for (rr int i=1,p=1;i<=n;p=++i){
for (rr int j=i+1;j<=n;++j)
if (a[j][i]>a[p][i]) p=j;
if (p!=i){
for (rr int j=1;j<=n;++j)
swap(a[i][j],a[p][j]);
ans=mod-ans;
}
if (!a[i][i]) return 0;
ans=1ll*ans*a[i][i]%mod;
rr int invt=ksm(a[i][i],mod-2);
for (rr int j=1;j<=n;++j)
if (i!=j){
rr int elim=1ll*a[j][i]*invt%mod;
for (rr int k=i;k<=n;++k)
Mo(a[j][k],1ll*elim*a[i][k]%mod);
}
}
return ans;
}
signed main(){
n=iut(),all=1<<(n-1);
for (rr int i=1;i<n;++i)
for (rr int CNT=iut();CNT;--CNT){
rr int x=iut(),y=iut();
++Aa[i][x][x],Mo(Aa[i][x][y],1);
++Aa[i][y][y],Mo(Aa[i][y][x],1);
}
for (rr int S=1;S<all;++S) xo[S]=xo[S&(S-1)]+1;
for (rr int S=1;S<all;++S){
memset(a,0,sizeof(a));
for (rr int k=0;k<n;++k)
if ((S>>k)&1){
for (rr int i=1;i<=n;++i)
for (rr int j=1;j<=n;++j)
MO(a[i][j],Aa[k+1][i][j]);
}
rr int t=Gauss(n-1);
if ((xo[S]^n)&1) MO(ans,t);
else Mo(ans,t);
}
return !printf("%d",ans);
}