# bzoj 4455 [Zjoi2016]小星星

### Input

n<=17,m<=n*(n-1)/2

4 3

1 2

1 3

1 4

4 1

4 2

4 3

6

### 题解

#include <cstdio>
#include <cstring>
using namespace std;
long long ans, f[20][20];
int n, m, x, y, v[20];
struct gra {
int tot, st[20];
struct edge {
int to, next;
}e[500];
void add(int x, int y) {
e[++tot].next = st[x];
e[tot].to = y, st[x] = tot;
}
}g, t;
void dfs(int now, int pre) {
for (int i = 1; i <= n; ++i)
if (!v[i]) f[now][i] = 1;
for (int i = t.st[now]; i; i = t.e[i].next)
if (t.e[i].to != pre) {
int to = t.e[i].to; dfs(to, now);
for (int j = 1; j <= n; ++j) {
long long sum = 0;
for (int k = g.st[j]; k; k = g.e[k].next)
sum += f[to][g.e[k].to];
f[now][j] *= sum;
}
}
}
long long solve() {
long long ans = 0;
memset(f, 0, sizeof f);
dfs(1, 0);
for (int i = 1; i <= n; ++i)
ans += f[1][i];
return ans;
}
void work(int now, int cnt) {
if (now > n) {
ans += ((cnt & 1) ? -1ll : 1ll) * solve();
return;
}
for (int i = 0; i <= 1; ++i)
v[now] = i, work(now + 1, cnt + i), v[now] = 0;
}
main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i)