int n, C[21], E[21][21], E2[21][21], C2[21], D[21], ck[21];
long long ret;
void DFS(int x, int d){
D[x] = d;
int i;
for (i = 0; i != C2[x]; i++){
if (!D[E2[x][i]])DFS(E2[x][i], d + 1);
}
}
void Do(int x, int A, int B){
if (x == n + 1){
ret += (long long)A*B;
return;
}
int i, j, chk;
for (i = 1; i <= 2; i++){
chk = 0;
for (j = 1; j != x; j++)D[j] = 0;
for (j = 0; j != C[x]; j++){
if (ck[E[x][j]] == i){
if (D[E[x][j]]){
if (D[E[x][j]] % 2 == 0)break;
}
else DFS(E[x][j], 1);
chk = 1;
}
}
if (j != C[x])continue;
for (j = 0; j != C[x]; j++){
if (ck[E[x][j]] == i){
E2[x][C2[x]++] = E[x][j];
E2[E[x][j]][C2[E[x][j]]++] = x;
}
}
if (!chk){
if (i)B *= 2; else A *= 2;
}
ck[x] = i;
Do(x + 1, A, B);
ck[x] = 0;
if (!chk){
if (i)B /= 2; else A /= 2;
}
for (j = 0; j != C[x]; j++){
if (ck[E[x][j]] == i){
C2[x]--, C2[E[x][j]]--;
}
}
}
}
long long NumberOfMaps(int N, int M, int *A, int *B){
int i;
for (i = 0; i < M; i++){
E[A[i]][C[A[i]]++] = B[i];
E[B[i]][C[B[i]]++] = A[i];
}
n = N;
Do(1, 1, 1);
return ret;
}
