#include <bits/stdc++.h>
using namespace std;
inline int getbit(int x, int i) {
return (x >> (i - 1)) & 1;
}
long long NumberOfMaps (int N, int M, int *A, int *B) {
vector<vector<int>> g(N + 1);
for (int i = 0; i < M; ++i) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
int si = 1 << N, mask;
long long res = 0;
vector<int> color;
bool sat;
function<void(int, int, int)> dfs = [&](int v, int c, int type) {
color[v] = c;
for (int u : g[v]) {
if (!sat) break;
if (getbit(mask, u) != type) continue;
if (color[u] == -1) {
dfs(u, c ^ 1, type);
} else if (color[u] == c) {
sat = false;
}
}
};
for (mask = 0; mask < si; ++mask) {
color.assign(N + 1, -1);
int cc = 0;
sat = true;
for (int i = 1; i <= N; ++i) {
if (color[i] == -1) {
dfs(i, 0, getbit(mask, i));
++cc;
}
}
res += sat * (1LL << cc);
}
return res;
}
