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