struct disj{
int pa[42];
void init(int n){
for(int i=1; i<=n; i++) pa[i] = i;
}
int find(int x){
return pa[x] = (pa[x] == x ? x : find(pa[x]));
}
bool uni(int p, int q){
p = find(p);
q = find(q);
if(p == q) return 0;
pa[q] = p;
return 1;
}
}disj;
long long NumberOfMaps (int N, int M, int *A, int *B){
long long sum = 0;
for(int i=0; i<(1<<(N-1)); i++){
disj.init(2*N);
bool bad = 0;
for(int j=0; j<M; j++){
if(((i >> (A[j] - 1)) & 1) == ((i >> (B[j] - 1)) & 1)){
disj.uni(A[j], B[j] + N);
disj.uni(B[j], A[j] + N);
if(disj.find(A[j]) == disj.find(A[j] + N)){
bad = 1;
break;
}
}
}
if(bad) continue;
int cnt = 0;
for(int i=1; i<=2*N; i++){
if(disj.uni(i, 1)){
cnt++;
}
}
cnt = (cnt + 1) / 2;
sum += (2 << cnt);
}
return sum;
}
