#include <bits/stdc++.h>
using namespace std;
struct DSU {
int n;
vector<int> p, sz;
DSU() = default;
DSU(int n) : n(n), p(n + 1, 0), sz(n + 1, 0) {}
void make_set(int v) {
p[v] = v;
sz[v] = 1;
}
void init() {
for (int i = 1; i <= n; ++i) make_set(i);
}
int find_set(int v) {
return v == p[v] ? v : p[v] = find_set(p[v]);
}
void union_sets(int u, int v) {
u = find_set(u);
v = find_set(v);
if (u != v) {
if (sz[u] < sz[v]) swap(u, v);
sz[u] += sz[v];
p[v] = u;
}
}
};
long long NumberOfMaps (int N, int M, int *A, int *B) {
vector<vector<int>> g(N + 1);
DSU dsu(N); dsu.init();
for (int i = 0; i < M; ++i) {
g[min(A[i], B[i])].push_back(max(A[i], B[i]));
dsu.union_sets(A[i], B[i]);
}
vector<bool> mark(N + 1);
vector<vector<int>> ccs(N + 1);
for (int i = 1; i <= N; ++i) {
ccs[dsu.find_set(i)].push_back(i);
}
long long cur;
// vector<int> color(N + 1, 0);
vector<vector<bool>> used(N + 1, vector<bool>(4, false));
function<void(int, int, int)> backtrack = [&](int s, int i, int sz) {
int v = ccs[s][i];
if (i == sz) {
++cur;
return;
}
// for (int x : g[v]) used[color[x] - 1] = true;
for (int j = 1; j <= 4; ++j) {
if (used[v][j - 1]) continue;
// color[v] = j;
bool ok = true;
vector<int> pre;
for (int x : g[v]) {
pre.push_back(used[x][j - 1]);
if (!used[x][j - 1]) {
used[x][j - 1] = true;
if (used[x][0]&&used[x][1]&&used[x][2]&&used[x][3]) {
ok = false;
}
}
}
if (ok) backtrack(s, i + 1, sz);
int k = 0;
for (int x : g[v]) {
used[x][j - 1] = pre[k];
++k;
}
// color[v] = 0;
}
};
long long res = 1;
for (int i = 1; i <= N; ++i) {
if (ccs[i].empty()) continue;
cur = 0;
backtrack(i, 0, ccs[i].size());
res *= cur;
}
return res;
}
