# bzoj 4596 [Shoi2016]黑暗前的幻想乡

### Output

#### 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

17

### 题解

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 20;
const int mod = 1000000007;
struct edge {
int to, next, from;
}e[N * N * N];
int st[N], f[N][N], a[N][N], tot, n, ans, p, x, y;
void add(int x, int y, int i) {
e[++tot].next = st[i];
e[tot].from = x;
e[tot].to = y, st[i] = tot;
}
int solve(int n) {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
a[i][j] = f[i][j];
int ans = 1;
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j)
while (a[j][i]) {
int t = a[i][i] / a[j][i];
for (int k = i; k <= n; ++k)
a[i][k] = (a[i][k] - (1ll * a[j][k] * t) % mod) % mod;
for (int k = i; k <= n; ++k)
swap(a[i][k], a[j][k]);
ans = -ans;
}
if (!a[i][i]) return 0;
ans = (1ll * ans * a[i][i]) % mod;
}
return ans;
}
void dfs(int now, int cnt) {
if (now == n) {
ans = (ans + ((cnt & 1) ? -1 : 1) * solve(n - 1)) % mod;
return;
}
dfs(now + 1, cnt);
for (int i = st[now]; i; i = e[i].next)
f[e[i].from][e[i].from]--, f[e[i].to][e[i].to]--,
f[e[i].from][e[i].to]++, f[e[i].to][e[i].from]++;
dfs(now + 1, cnt + 1);
for (int i = st[now]; i; i = e[i].next)
f[e[i].from][e[i].from]++, f[e[i].to][e[i].to]++,
f[e[i].from][e[i].to]--, f[e[i].to][e[i].from]--;
}
main() {
scanf("%d", &n);
for (int i = 1; i < n; ++i) {
scanf("%d", &p);
for (int j = 1; j <= p; ++j)
scanf("%d%d", &x, &y),