#include <bits/stdc++.h>
using namespace std;
void read(long long &x) {
  x = 0;
  long long f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -f;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  x *= f;
}
void print(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (!x) return;
  print(x / 10), putchar(x % 10 + 48);
}
void write(long long x) {
  if (!x)
    putchar('0');
  else
    print(x);
  putchar('\n');
}
const long long maxn = 40 + 10;
const long long inf = 1e9;
const double eps = 1e-8;
const long long mod = 1e9 + 7;
long long head[maxn], tot, d[maxn], n, m;
struct edge {
  long long to, nxt;
} e[10000];
void ins(long long u, long long v) {
  e[++tot] = (edge){v, head[u]}, head[u] = tot;
  d[v]++;
}
long long qpow(long long a, long long x) {
  long long res = 1;
  for (; x; x >>= 1, a = a * a)
    if (x & 1) res = res * a;
  return res;
}
namespace search {
long long f[(1 << 21) + 10], t[maxn], w, g[(1 << 21) + 10];
void dfs(long long x, long long s, long long v) {
  if (x == w + 1) return f[s] = v, void();
  dfs(x + 1, s, v);
  t[x] = 1;
  for (long long i = head[x]; i; i = e[i].nxt) {
    long long r = e[i].to;
    if (r < x && t[r]) v = -1;
    if (r > w && ~v) v |= 1 << (r - w - 1);
  }
  dfs(x + 1, s | (1 << (x - 1)), v);
  t[x] = 0;
}
void dfs2(long long x, long long s, long long v) {
  if (x == n + 1) return g[s] = v, void();
  dfs2(x + 1, s, v);
  t[x] = 1;
  for (long long i = head[x]; i; i = e[i].nxt) {
    long long r = e[i].to;
    if (r < x && r > w && t[r]) v = 0;
  }
  dfs2(x + 1, s | (1 << (x - 1 - w)), v);
  t[x] = 0;
}
void fwt(long long *r, long long N) {
  for (long long i = 1; i < N; i <<= 1)
    for (long long j = 0; j < N; j += i << 1)
      for (long long k = 0; k < i; k++) r[i + j + k] += r[j + k];
}
long long solve() {
  w = n / 2;
  dfs(1, 0, 0);
  dfs2(w + 1, 0, 1);
  fwt(g, 1 << (n - w));
  long long ans = 0;
  for (long long s = 0; s < 1 << w; s++)
    if (~f[s]) ans += g[(1 << (n - w)) - 1 - f[s]];
  return ans;
}
}  // namespace search
long long vis[maxn], cnt;
void dfs1(long long x) {
  vis[x] = 1;
  for (long long i = head[x]; i; i = e[i].nxt)
    if (!vis[e[i].to]) dfs1(e[i].to);
}
long long get3() {
  long long ans = 1;
  for (long long i = 1; i <= n; i++)
    if (!vis[i]) ans <<= 1, dfs1(i);
  return ans;
}
long long get13() {
  long long ans = 1;
  for (long long i = 1; i <= n; i++)
    if (!d[i]) ans *= 2;
  return ans;
}
long long bo;
void dfs2(long long x, long long c) {
  vis[x] = c;
  for (long long i = head[x]; i; i = e[i].nxt)
    if (!vis[e[i].to])
      dfs2(e[i].to, -c);
    else if (vis[e[i].to] == c)
      bo = 1;
}
long long get12() {
  memset(vis, 0, sizeof vis);
  for (long long x = 1; x <= n; x++)
    if (!vis[x]) dfs2(x, 1);
  if (bo) return 0;
  memset(vis, 0, sizeof vis);
  return get3();
}
signed main() {
  read(n), read(m);
  if (!m) return puts("0"), 0;
  for (long long i = 1, x, y; i <= m; i++)
    read(x), read(y), ins(x, y), ins(y, x);
  long long ans = qpow(2, n);
  ans -= search::solve() * 2, ans -= get3();
  ans += get13() * 2;
  ans += get12();
  printf("%lld\n", ans);
  return 0;
}
