//
//  main.cpp
//  ABC 195
//
//  Created by Paul Liao on 2021/3/13.
//

#include <iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<map>
#define ll long long
using namespace std;
vector<int> e[21];
int vis[21];
int col[21];
ll dp[21][4],ans=0;
bool uu[21]={0};
int n,m;
bool check(int u){
    for(int i:e[u]) if(col[u]==col[i]) return 0;
    return 1;
}
void dfs(int now){
    vis[now]=1;
    if(now==n+1) {
        ans++;
        return;
    }
    if(!uu[now]){
        dfs(now+1);
        return ;
    }
    for(int i=1;i<=3;i++){
        col[now]=i;
        if(check(now)) dfs(now+1);
        col[now]=0;
    }
}

int main() {
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        uu[a]=1;
        uu[b]=1;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    dfs(1);
    for(int i=1;i<=n;i++) if(!uu[i]) ans*=3ll;
    cout<<ans<<endl;
    
}

/** これを翻訳している間、あなたはあなたの人生のいくつかの貴重な瞬間を無駄にしました **/
#include<bits/stdc++.h>
using namespace std;

#define rep(i,x,y) for(int i=x;i<y;i++)
#define repr(i,x,y) for(int i=x;i>=y;i--) 
#define int long long
#define pb push_back
#define ff first
#define ss second
#define sz(x) ((int)x.size())
#define all(x) begin(x), end(x)
#define memo(x,y) memset((x),(y),sizeof((x)))
#define line cout<<"[At "<<__LINE__<<"]"<<endl;

using pii = pair<int,int>;
using vi = vector<int>;
using vii = vector<pair<int,int>>;

constexpr int mod = 1e9 + 7 , N = 2e5 + 5;
constexpr long long inf = 1e18;
constexpr long double eps = 1e-6; 

vector<int> g[N];
int node1 = -1,maxd= -1;
void dfs1(int v,int p,int d){
  // cout<<v<<"=="<<d<<endl;
  if(d>maxd){
    node1=v;
    maxd=d;
  }
  for(auto &x:g[v]){
    if(x!=p)
      dfs1(x,v,d+1);
  }
}
int mark[N];
int E[N];
bool markdfs(int v,int p,int B){
  for(auto &x:g[v]){
    if(x!=p){
      if(markdfs(x,v,B)){
        mark[v]=1;
        return true;
      }
    }
  }
  if(v==B)
    mark[v]=true;
  return mark[v];
}
void dfs(int v,int p,int &num){
  E[v]=num;
  for(auto &x:g[v]){
    if(x!=p && mark[x] == 0){
        num++;
        dfs(x,v,num);
    }
  }
  for(auto &x:g[v]){
    if(x!=p && mark[x] == 1){
        num++;
        dfs(x,v,num);
    }
  }
  num++;
}
void Onigiri()
{
  int n;
  cin>>n;
  rep(i,0,n-1){
    int x,y;
    cin>>x>>y;
    x--,y--;
    g[x].pb(y);
    g[y].pb(x);
  }

  dfs1(0,-1,0);
  int A=node1;
  maxd=-1;
  dfs1(node1,-1,0);
  int B=node1;
  markdfs(A,-1,B);

  // cout<<A<< " "<<B<<endl;
  int num = 1;
  dfs(A,-1,num);

  rep(i,0,n){
    cout<<E[i]<<" ";
  }
}
signed main()
{
   ios_base::sync_with_stdio(false);cin.tie(NULL);
   //cout.precision(10);cout<<fixed;
   #ifdef Zoro
   freopen("/home/pritish/Competitive/in", "r", stdin);
   freopen("/home/pritish/Competitive/out", "w", stdout);
   #endif  
 
   int t=1; 
   //cin>>t;
 
   while(t--)
   {Onigiri();cout<<"\n";}

   cerr<<"\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
   return 0;
}