#include <bits/stdc++.h>
using namespace std;

long long color3(const vector<vector<int>> G,vector<int> c){
  bool ok;
  long long ans=0;
  if(c.size()==G.size()) return 1;
  for(int i=0;i<3;i++){
    ok=1;
    for(int j:G.at(c.size())){
      if(j<c.size()&&c.at(j)==i){
        ok=0;
        break;
      }
    }
    if(ok){
      c.push_back(i);
      ans+=color3(G,c);
      c.pop_back();
    }
  }
  return ans;    
}

int main(){
  int N,M,A,B;
  cin >> N >> M;
  vector<vector<int>> G(N);
  for(int i=0;i<M;i++){
    cin >> A >> B;
    A--;
    B--;
    G.at(A).push_back(B);
    G.at(B).push_back(A);
  }
  long long ans=1;
  vector<int> done(N,-1);
  for(int i=0;i<N;i++){
    if(done.at(i)>-1) continue;
    vector<int> VC;
    queue<int> que;
    done.at(i)=VC.size();
    VC.push_back(i);
    que.push(i);
    while(que.size()){
      for(int j:G.at(que.front())){
        if(done.at(j)>-1) continue;
        done.at(j)=VC.size();
        VC.push_back(j);
        que.push(j);
      }
      que.pop();
    }
    if(VC.size()<3){
      ans*=3*VC.size();
      continue;
    }
    vector<vector<int>> GC(VC.size());
    for(int j=0;j<VC.size();j++){
      for(int k:G.at(VC.at(j))){
        GC.at(j).push_back(done.at(k));
      }
    }
    ans*=6*color3(GC,{0,1});
  }
  cout << ans << endl;
}
#include <bits/stdc++.h>

using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define debug(output) if(debugFlag)cout<<#output<<"= "<<output<<endl
using lint = long long;
typedef pair<int,int> P;
const bool debugFlag=true;
const lint linf=1e18+7;
const lint inf=1e9+7;
const int MOD=1000000007;

signed main(){
  int n,m;cin>>n>>m;
  vector<set<int>> edge(n);
  rep(i,m){
      int a,b;cin>>a>>b;
      --a;--b;
      edge[a].insert(b);
      edge[b].insert(a);
  }
  lint res=0;
  auto binary_graph=[&](vector<int>const& h,int& sm)->bool{
      int hn=h.size();
      vector<int> memo(hn,0);
      vector<vector<int>> edge2(hn);
      rep(i,hn){
          for(int j=i+1;j<hn;++j){
              if(edge[h[i]].find(h[j])!=edge[h[i]].end()){
                  edge2[i].push_back(j);
                  edge2[j].push_back(i);
              }
          }
      }
      rep(st,hn){
          if(memo[st]>0)continue;
          queue<int> que;
          que.push(st);
          ++sm;
          memo[st]=1;
          while(!que.empty()){
              int no=que.front();que.pop();
              for(auto& e:edge2[no]){
                  if(memo[e]==0){
                      memo[e]=3^memo[no];
                      que.push(e);
                  }
                  else if(memo[e]==memo[no])return false;
              }
          }
      }
      return true;
  };
  rep(bit,(1<<n)){
      vector<int> g,h;
      rep(i,n){
          if(bit&(1<<i))g.push_back(i);
          else h.push_back(i);
      }
      bool flag=false;
      rep(i,g.size()){
          for(int j=i+1;j<g.size();++j){
              if(edge[g[i]].find(g[j])!=edge[g[i]].end())flag=true;
          }
      }
      if(flag)continue;
      int cnt=0;
      if(binary_graph(h,cnt)){
          res+=(1<<cnt);
          //debug(bit);
          //debug((1<<cnt));
      }
  }
  cout<<res<<"\n";
  return 0;
}
/*
5 4
1 2
2 3 
3 4
4 5
18
*/