矩阵树定理+模意义下整数高斯消元
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int n, uu, vv, ww, w[21][21];
const int mod=1e9+7;
vector<pii> vec[21];
int getGcd(int a, int b){
return !b?a:getGcd(b, a%b);
}
int getLcm(int a, int b){
return a/getGcd(a, b)*b;
}
int gauss(){
int bei=1;
for(int i=1; i<n; i++){
for(int j=i+1; j<n; j++){
while(w[j][i]){
ll t=w[i][i]/w[j][i];
for(int k=i; k<n; k++)
w[i][k] = (w[i][k] - (ll)w[j][k]*t%mod + mod) % mod;
swap(w[i], w[j]);
bei *= -1;
}
}
if(!w[i][i]) return 0;
}
for(int i=1; i<n; i++)
bei = (ll)bei * w[i][i] % mod;
return bei;
}
int main(){
cin>>n;
for(int i=1; i<n; i++){
scanf("%d", &ww);
while(ww--){
scanf("%d %d", &uu, &vv);
vec[i].push_back(make_pair(uu, vv));
}
}
int ans=0;
for(int i=0; i<(1<<(n-1)); i++){//i: which companys don't xiujian
memset(w, 0, sizeof(w));
int cnt=0;
for(int j=1; j<n; j++)
if(!(i&(1<<(j-1)))){
cnt++;
for(int k=0; k<vec[j].size(); k++){
uu = vec[j][k].first; vv = vec[j][k].second;
w[uu][uu]++; w[vv][vv]++;
w[uu][vv]--; w[vv][uu]--;
}
}
int re=gauss();
cnt = n - 1 - cnt;
if(cnt&1) re *= -1;
ans = (ans + re) % mod;
ans = (ans + mod) % mod;
}
cout<<ans<<endl;
return 0;
}