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 Clear(int x){
int i;
for (i = 0; i < C2[x]; i++){
C2[E2[x][i]]--;
}
C2[x] = 0;
}
void Do(int x){
if (x == n + 1){
int i, t = 1;
for (i = 1; i != x; i++)D[i] = 0;
for (i = 1; i != x; i++){
if (!D[i])DFS(i, 1), t *= 2;
}
ret = ret + t;
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 = E[x][j];
E2[x][C2[x]++] = chk, E2[chk][C2[chk]++] = x;
}
}
}
if (j != C[x]){
Clear(x);
continue;
}
ck[x] = i;
Do(x + 1);
ck[x] = 0;
Clear(x);
}
}
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);
return ret;
}
