/*
WA因：状压13位而不是12位 
*/

#include <bits/stdc++.h>

using namespace std;

const int N = 55;

int n, m;
bool G[N][N];
int f[2][1600000];    // 滚一下 
int pw[N];

void add(int &a, int b) {
  a = (a + b) % 4;
}

signed main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//  freopen("data.in", "r", stdin);
//  freopen("res.out", "w", stdout);
  
  cin >> n >> m;
  
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    G[u][v] = G[v][u] = 1;
  }
  
  pw[0] = 1;
  for (int i = 1; i <= 13; i++) pw[i] = pw[i - 1] * 3;
  
  f[1][0] = f[1][1] = f[1][2] = 1;
  for (int cnt = 1, i = 1; cnt < n; cnt++, i = !i) {
    int t = min(13, i);
    for (int j = 0; j < pw[t]; j++) {
      int nj = (j - pw[12] * (j / pw[12])) * 3;   // 注意要超出13位才去尾 
//      printf("nj:%d\n", nj);
      bool flag0 = 1, flag1 = 1;    // 能否为黑或白 
      for (int k = 0; k < t; k++) {
        if (G[i + 1][i - k]) {
          int bit = j / pw[k] % 3;
          if (bit == 0) flag1 = 0;
          else if (bit == 1) flag0 = 0;
        }
      }
      if (flag0) add(f[i + 1][nj + 0], f[i][j]);
      if (flag1) add(f[i + 1][nj + 1], f[i][j]);
      add(f[i + 1][nj + 2], f[i][j]);
      f[i][j] = 0;      // 滚动数组要清这个 
//      printf("f[%d][%d]:%d\n", i, j, f[i][j]);
    }
  }
  
  int ans = 0;
  for (int j = 0; j < pw[min(13, n)]; j++) {
//    printf("f[%d][%d]:%d\n", n, j, f[n][j]);
    add(ans, f[n & 1][j]);
  }
  
  cout << ans / 2;
  
  return 0;
}

/*
3 3
1 2
2 3
3 1


*/