C++(clang++ 11.0.1) 解法, 执行用时: 303ms, 内存消耗: 460K, 提交时间: 2023-05-04 18:32:54

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>

const int N = 20, mod = 1e9+7;

typedef long long ll;

ll g[N][N];
std::vector<std::pair<int,int>> h[N];

int calc(int n)
{
	auto qpw = [&](int x, int k, int mod) {
		int res = 1;
		while(k) {
			if(k&1) res = (1ll*res*x)%mod;
			k >>= 1;
			x = 1ll*x*x%mod;
		}
		return res;
	};

	ll res = 1;
	for(int i=0;i<n;i++)
	{
		int t = 0;
		if(g[i][i]==0) {
			for(int j=i+1;j<n;j++) {
				t ++;
				if(g[j][i]) {
					std::swap(g[j],g[i]);
					break;
				}
			}
			return 0;
		}
	
		for(int j=i+1;j<n;j++)
		{
			auto fac = (-qpw(g[i][i],mod-2,mod)*g[j][i]%mod+mod)%mod;
			for(int k=i;k<n;k++) (g[j][k] += fac*g[i][k]) %= mod;
		}
		(res *= g[i][i])%=mod;
		if(t%2) res = -res+mod;
		if(res<0) res += mod;
		//std::cout << n << " "  << i << " " << res << "?\n";
	}

	return res;
}

void solve()
{
	int n;
	std::cin >> n;

	for(int i=0;i<n-1;i++)
	{
		int m;
		std::cin >> m;
		while(m --)
		{
			int u, v;
			std::cin >> u >> v;
			u --, v --;
			h[i].push_back({u,v});
		}
	}

	int ans = 0;
	for(int i=0;i<1<<(n-1);i++)
	{
		int all = 0;

		memset(g,0,sizeof g);
		for(int j=0;j<n-1;j++) if(i>>j&1) {
			all ++;
			for(auto [u,v]:h[j])
			{
				g[u][v] --, g[v][u] --;
				g[u][u] ++, g[v][v] ++;
			}
		}
		if((n-1)%2==all%2) (ans += calc(n-1)) %= mod;
		else (ans -= calc(n-1))%= mod;

		if(ans<0) ans += mod;
	}
	std::cout << ans << "\n";
}

signed main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);

	int t = 1;
	while(t --)
		solve();
	return 0;
}