看到数据范围猜复杂度是 \(O(\text{poly}(n) 2^{\frac{n}{2}})\)，所以考虑折半。
至少有一个端点被选不好算，考虑转成两个端点都被选，但是边数奇偶性与 \(m\) 相同。
称编号 \(< \frac{n}{2}\) 的点为左点，编号 \(\ge \frac{n}{2}\) 的点为右点（点编号从 \(0\) 开始）
设 \(f_S\) 为只考虑左点，点集 \(S\) 的导出子图边数奇偶性，\(g_S\) 为只考虑右点，点集 \(S\) 的导出子图边数奇偶性，\(a_S\) 为右点中与左点点集 \(S\) 连边数量是奇数的点集，题目即求：
\[\sum\limits_{S, T} [f_S \oplus g_T \oplus (|a_S \cap T| \bmod 2) = m \bmod 2] \]其中 \(|a_S \cup T| \bmod 2\) 是在求 \(S, T\) 之间边数的奇偶性。
考虑枚举 \(f_S = x, g_T = y\)，设 \(z = (m \bmod 2) \oplus x \oplus y\) 即 \(|a_S \cap T|\) 的奇偶性。那么就是要算：
\[\sum\limits_{S, T} ([f_S = x] \times [g_T = y] \times [|a_S \cap T| \bmod 2 = z] \]考虑计算 \(h_P = \sum\limits_{S, T} [a_S \cap T = P] \times [f_S = x] \times [g_T = y]\)。设 \(b_P = \sum\limits_{S} [a_S = P] \times [f_S = x], c_P = [g_P = y]\)，那么：
\[h_P = \sum\limits_{S \cap T = P} b_S \times c_T \]这样就化成了一个比较标准的按位与卷积形式，FWT 即可。
时间复杂度 \(O((n + m) 2^{\frac{n}{2}})\)，常数比较大。
code
// Problem: H - Security Camera
// Contest: AtCoder - AtCoder Beginner Contest 220
// URL: https://atcoder.jp/contests/abc220/tasks/abc220_h
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 45;
const int maxm = (1 << 20) + 100;
int n, m, all, f[maxm], g[maxm], a[maxm], to[maxn];
ll ff[maxm], gg[maxm];
vector<int> vc[maxm];
pii e1[maxm], e2[maxm];
inline void FWT(ll *f, int x) {
for (int k = 1; k < all; k <<= 1) {
for (int i = 0; i < all; i += (k << 1)) {
for (int j = 0; j < k; ++j) {
f[i + j] += f[i + j + k] * x;
}
}
}
}
void solve() {
scanf("%d%d", &n, &m);
int m1 = 0, m2 = 0;
for (int _ = 0, u, v; _ < m; ++_) {
scanf("%d%d", &u, &v);
--u;
--v;
if (u > v) {
swap(u, v);
}
if (u < n / 2 && v >= n / 2) {
to[v] |= (1 << u);
} else if (u < n / 2 && v < n / 2) {
e1[++m1] = make_pair(u, v);
} else {
e2[++m2] = make_pair(u, v);
}
}
for (int S = 0; S < (1 << (n / 2)); ++S) {
for (int i = 1; i <= m1; ++i) {
int u = e1[i].fst, v = e1[i].scd;
if ((S & (1 << u)) && (S & (1 << v))) {
f[S] ^= 1;
}
}
}
for (int S = 0; S < (1 << (n - n / 2)); ++S) {
for (int i = 1; i <= m2; ++i) {
int u = e2[i].fst, v = e2[i].scd;
if ((S & (1 << (u - n / 2))) && (S & (1 << (v - n / 2)))) {
g[S] ^= 1;
}
}
}
for (int S = 0; S < (1 << (n / 2)); ++S) {
for (int i = n / 2; i < n; ++i) {
if (__builtin_parity(to[i] & S)) {
a[S] |= (1 << (i - n / 2));
}
}
vc[a[S]].pb(S);
}
all = (1 << (n - n / 2));
ll ans = 0;
for (int x = 0; x <= 1; ++x) {
for (int y = 0; y <= 1; ++y) {
for (int S = 0; S < all; ++S) {
ff[S] = 0;
for (int T : vc[S]) {
ff[S] += (f[T] == x);
}
gg[S] = (g[S] == y);
}
FWT(ff, 1);
FWT(gg, 1);
for (int i = 0; i < all; ++i) {
ff[i] *= gg[i];
}
FWT(ff, -1);
for (int i = 0; i < all; ++i) {
if ((__builtin_parity(i) ^ x ^ y) == (m & 1)) {
ans += ff[i];
}
}
}
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}