#include <bits/stdc++.h>          
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repp(i, st, en) for (ll i = (ll)st; i < (ll)(en); i++)
#define repm(i, st, en) for (ll i = (ll)st; i >= (ll)(en); i--)
#define all(v) v.begin(), v.end()
void chmax(ll &x, ll y) {x = max(x,y);}
void chmin(ll &x, ll y) {x = min(x,y);}
void Yes() {cout << "Yes" << endl; exit(0);}
void No() {cout << "No" << endl; exit(0);}
template<class in_Cout> void Cout(in_Cout x) {cout << x << endl; exit(0);}
template<class in_vec_cout>
void vec_cout(vector<in_vec_cout> vec) {
    for (in_vec_cout res : vec) {cout << res << " ";}
    cout << endl;
}

const ll inf = 1e18;
const ll mod = 1e9 + 7;

ll N, M;
vector<vector<ll>> G;
vector<ll> nodes, col;
vector<bool> seen;
ll tmp = 0;

void init() {
    cin >> N >> M;
    G.resize(N);
    rep(i,M) {
        ll a, b; cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    col.resize(N,-1);
    seen.resize(N,false);
}

void make_nodes(ll x) {
    seen[x] = true;
    nodes.push_back(x);
    for (ll y : G[x]) {
        if (seen[y]) continue;
        make_nodes(y);
    }
}

void dfs(ll id) {
    if (id==nodes.size()) {
        tmp++;
        return;
    }
    ll now = nodes[id];
    vector<bool> used(3);
    for (ll to : G[now]) {
        if (col[to]==-1) continue;
        used[col[to]] = true;
    }
    rep(c,3) {
        if (used[c]) continue;
        col[now] = c;
        dfs(id+1);
        col[now] = -1;
    }
}

ll solve(ll st) {
    nodes.resize(0);
    make_nodes(st);
    tmp = 0;
    col[st] = 0;
    dfs(1);
    return 3 * tmp;
}

int main() {
    init();
    ll ans = 1;
    rep(i,N) {
        if (seen[i]) continue;
        ll res = solve(i);
        ans *= res;
    }
    Cout(ans);
}
#include<bits/stdc++.h>
using namespace std;

#define ll  int
#define ull unsigned  long long
#define pll  pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
const ll maxn =7e5+100;
const ll mod=1e9+7 ;
const ll base=2e18;
vector<ll> adj[maxn];
ll col[23];
ll n;
bool dd[23];

namespace ufs {
  struct node {int fa, val, size;} t[30];
  struct info {int x, y; node a, b;} st[30];
  inline void pre() {for(int i=1; i<=n; i++) t[i] = (node){i, 0, 1};}
  inline int find(int x) {while(t[x].fa != x) x = t[x].fa; return x;}
  inline int dis(int x) {
    int ans=0;
    while(t[x].fa != x) ans ^= t[x].val, x = t[x].fa;
    return ans;
  }
  inline void link(int x, int y) {
    int val = dis(x) ^ dis(y) ^ 1;
    x = find(x); y = find(y);
    if(t[x].size > t[y].size) swap(x, y);
    t[x].fa = y; t[x].val = val; t[y].size += t[x].size;
  }

} using namespace ufs;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp","r"))
    {
        freopen("test.inp","r",stdin);
        freopen("test.ans","w",stdout);
    }
    ll  m;
     cin>> n>> m ;
     for (int i=1;i<=m;i++)
     {
         ll x, y;
          cin>>x>> y;
          x--;
          y--;
          adj[x].pb(y);
          adj[y].pb(x);
     }
     long long  ans=0;
     for (int i=0;i<(1ll<<n);i++)
     {
         for (int j=0;j<n;j++)
         {
             if (i&(1ll<<j))
             {
                 col[j]=1;
             }
             else
             {
                 col[j]=0;
             }
         }
         bool kt=true;
         pre();
         for (int i=0;i<n;i++)
         {
             for (auto to:adj[i])
             {
                 if (col[to]==col[i]&&col[to]==0)
                 {
                     kt=false;
                     break;
                 }
                 if (col[to]==col[i]&&col[to]==1)
                 {
                     ll x=find(to+1);
                     ll y=find(i+1);
                     if (x==y)
                     {
                         ll h=dis(to+1)^dis(i+1);
                         if (h==0)
                         {
                             kt=false;
                             break;
                         }
                     }
                     else link(to+1,i+1);
                 }
             }
             if (!kt) break;
         }
         if (!kt)
         {
             continue;
         }
         for (int i=1;i<=n;i++) dd[i]=0;
         long long res=1;
         for (int i=1;i<=n;i++)
         {
             if (col[i-1]==0) continue;
             ll t=find(i);
             if (dd[t]) continue;
             dd[t]=1;
             res*=2;
         }
         ans+=res;
     }
     cout <<ans<<endl;
}


