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

#define fr(i,n) for(int i = 0; i<n; i++)
#define sz(v) (int)(v.size())
#define prin(a) cout << #a << " = " << a << endl
#define prinv(v) cout << #v << " = "; for(auto it : v) cout << it << ", "; cout << endl
#define all(v) (v).begin(),(v).end()

typedef long long ll;

#define rmin(a,b) a = min<ll>(a,b)
#define rmax(a,b) a = max<ll>(a,b)

#define fi first
#define se second

const int N = 25;
vector<int> g[N];

int ne, nv;
int ja_comp[N];
int cor[N];

vector<int> vno;
int ant[N];

void dfscnt(int no,int from){
	if(ja_comp[no]) return;
	ant[no] = from;
	ja_comp[no] = 1;
	vno.push_back(no);
	nv++;
	ne+=sz(g[no]);
	for(auto &it : g[no]) dfscnt(it,no);
}

/*
void dfs(int no){
	if(vis[no]) return;
	vis[no] = 1;
	na++;
	fr(c,3){
		int bad = 0;
		for(auto &it : g[no]){
			if(vis[it] and cor[it]==c){
				bad = 1;
				break;
			}
		}
		if(bad) continue;
		if(na==nv){
			ways++;
		} else{
		
		}
	}
	na--;
	vis[no] = 0;
}
*/

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m;
	fr(mm,m){
		int a, b; cin >> a >> b;
		a--,b--;
		g[a].push_back(b);		
		g[b].push_back(a);		
	}
	
	ll ans = 1;
	
	int ctc[3][2] = {{1,2},{0,2},{0,1}};
	fr(noo,n){
		if(!ja_comp[noo]){
			nv = 0, ne = 0;
			vno.clear();
			dfscnt(noo,-1);
			//prin(noo);
			//prin(nv);
			//prinv(vno);
			/*
			if(2*nv-2==ne){
				ll cur = 3;
				fr(i,nv-1) cur*=2;
				ans*=cur;
			} else{
				na = 0;	
				dfs(i);
				ans*=ways;
			}
			*/
			ll cur = 0;
			fr(c1,3){
				cor[vno[0]] = c1;
				fr(mask,1<<(nv-1)){
					//prin(mask);
					fr(i,nv-1){
						int cc = cor[ant[vno[i+1]]];
						if(mask&(1<<i)){
							cor[vno[i+1]] = ctc[cc][0];
						} else{
							cor[vno[i+1]] = ctc[cc][1];
						}
					}
					int ok = 1;
					for(auto &no : vno){
						for(auto &it : g[no]){
							if(cor[it]==cor[no]){
								ok = 0;
								goto sai;
							}
						}
					}
					sai:
					if(ok) cur++;
				}
			}
			ans*=cur;
		}
	}
	
	cout << ans << "\n";
}
#include <bits/stdc++.h>

using namespace std;

/*
    VERIFICAR:
    - Corner cases
    - Estouro de variavel
    - Acesso indevido de memoria
    
    MODULO NEGATIVO
    int modulo(int x,int N){
        return (x % N + N) %N;
    }

*/

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define f first
#define s second
#define pb push_back

typedef long long ll;
typedef pair<int, int> ii;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;

struct info {
    bool c1;
    bool c2;
    bool c3;
};

int n;
vector<vector<int> > g;
vector<int> cores;
ll cont = 0;
vector<int> analisado;
vector<info> opt;

void solve(int at1) {
    if(at1 == analisado.size()) {
        cont++;
        return;
    }
    int at = analisado[at1];
    bool cor1 = opt[at].c1;
    bool cor2 = opt[at].c2;
    bool cor3 = opt[at].c3;
    if(!cor1) {
        cores[at] = 0;
        vector<info> old = opt;
        for(int viz : g[at]) {
            opt[viz].c1 = true;
        }
        solve(at1+1);
        opt = old;
        cores[at] = -1;
    }
    if(!cor2) {
        cores[at] = 1;
        vector<info> old = opt;
        for(int viz : g[at]) {
            opt[viz].c2 = true;
        }
        solve(at1+1);
        opt = old;
        cores[at] = -1;
    }
    if(!cor3) {
        cores[at] = 2;
        vector<info> old = opt;
        for(int viz : g[at]) {
            opt[viz].c3 = true;
        }
        solve(at1+1);
        opt = old;
        cores[at] = -1;
    }
}

vector<bool> vis;

void dfs(int at, int pai) {
    if(vis[at]) {
        return;
    }
    vis[at] = true;
    for(int viz: g[at]) {
        if(viz != pai) {
            dfs(viz, at);
        }
    }
}

int main() {_
    int m;
    cin >> n >> m;
    g.resize(n);
    int a, b;
    for(int I=0; I<m; I++) {
        cin >> a >> b;
        a--; b--;
        g[a].pb(b);
        g[b].pb(a);
    }
    vector<bool> visAq(n, false);
    vector<vector<int> > componentes;
    for(int I=0; I<n; I++) {
        if(!visAq[I]) {
            vis.clear();
            vis.resize(n);
            dfs(I, -1);
            vector<int> componente;
            for(int J=0; J<n; J++) {
                if(vis[J]) {
                    visAq[J] = true;
                    componente.pb(J);
                }
            }
            componentes.pb(componente);
        }
    }
    ll resp = 1;
    cores.resize(n, -1);
    opt.resize(n);
    for(vector<int> v : componentes) {
        if(v.size() == 1) {
            resp*=3;
        } else {
            cont = 0;
            analisado = v;
            solve(0);
            resp*=cont;
        }
        if(resp == 0) {
            break;
        }
    }
    cout << resp << endl;
	return 0;
}
