// Atcoder.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//


#define _USE_MATH_DEFINES

#include<math.h>
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
#include <sstream>



using namespace std;
typedef long long ll;
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i,n) for(int i=0;i<n;i++)
#define show(s) cout<<s<<endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define LINF (1LL << 50)
#define MOD (1e9+7)
#define rrep(i,n) for(int i=n-1;i>=0;--i)

//typedef pair < ll, ll> P;

//元がintの分けたものを返す p[0]は1桁目
vector<int> divnum(ll num) {
	int dig;
	vector<int>p;
	while (num) {
		dig = num % 10;
		p.push_back(dig);
		num /= 10;
	}
	return p;
}
//桁数を返す
int digiter(ll num) {
	int dig;
	vector<int>p;
	while (num) {
		dig = num % 10;
		p.push_back(dig);
		num /= 10;
	}
	return p.size();
}
//元がstringの分けたものを返す d[0]は最高位
vector<int> convertstring(string s) {
	vector<int> d;
	ll n = s.size();
	reverse(s.begin(), s.end());
	rep(i, n) {
		d.push_back(s[i] - '0');
	}
	return d;
}

/*long double　は%Lf*/
//queue古い順,stack新しい
/****Union-Find-Tree***/
int par[int(0x7ffffff)];//Parent
int Rank[int(0x7ffffff)];//Deep_of_the_Tree



//n要素で初期化
void init(int n) {
	for (int i = 0; i < n; i++) {
		par[i] = i;
		Rank[i] = 0;
	}
}
//木の根探し
int find(int x) {
	if (par[x] == x) {
		return x;
	}
	else {
		return par[x] = find(par[x]);
	}
}
//xとyの属する集合を併合
void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y)return;

	if (Rank[x] < Rank[y]) {
		par[x] = y;
	}
	else {
		par[y] = x;
		if (Rank[x] == Rank[y])Rank[x]++;
	}
}

bool same(int x, int y) {
	return find(x) == find(y);
}

int N, M;
vector<int>G[25]; int V[25],id[25]; int c = 0;
int color[25]; bool used[25];
bool dfs(int u,int prec) {
	
	if (used[u])return true;

	if (c >> id[u] & 1) {
		prec += 2; prec %= 3;
	}
	else {
		prec++; prec %= 3;
	}
	for (int to : G[u]) {
		if (used[to] && color[to] == prec)return false;
	}
	color[u] = prec;
	used[u] = true;
	for(int to : G[u]) {
		if (!dfs(to, prec))return false;
	}
	return true;

}
int32_t main() {
	cin >> N >> M;
	init(N);
	rep(i, M) {
		int a, b; cin >> a >> b;
		a--; b--;
		unite(a, b);
		G[a].push_back(b); G[b].push_back(a);
	}
	rep(i, N) {
		id[i] = V[find(i)];
		V[find(i)]++;
	}
	ll res = 1;
	rep(i, N) {
		if (V[i]==0)continue;
		ll cnt = 0;
		rep(j, (1 << V[i])) {
			c = j;
			rep(k, 3) {
				fill(color, color + 22, -1);
				fill(used, used + 22, false);
				color[i] = k; used[i] = true;
				bool flag = true;
				for (int to : G[i]) {
					if (!dfs(to, k))flag = false;
				}
				cnt += flag;
			}
		}
		cnt /= 2LL;
		res *= cnt;
	}
	cout << res << endl;
}
#include<bits/stdc++.h>
#define MAX 20
#define MOD 1000000007
using namespace std;
vector<int> v[MAX+10];
int c[MAX+10];
bool vis[MAX+10];
bool dfs(int x)
{
	vis[x] = true;
	bool ans = true;
	for(int y:v[x])
	{
		if(c[y]==-1)
			continue;
		if(vis[y])
			ans = ans&&(c[x]!=c[y]);
		else
			c[y] = 1-c[x], ans = ans&&dfs(y);
	}
	return ans;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,m;
	cin>>n>>m;
	while(m--)
	{
		int x,y;
		cin>>x>>y;
		--x, --y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	int lmt = 1<<n;
	long long ans = 0;
	for(int i=0;i<lmt;++i)
	{
		for(int j=0;j<n;++j)
		{
			if(i&(1<<j))
				c[j] = -1;
			else c[j] = 0;
			vis[j] = false;
		}
		long long tmp = 1;
		bool ok = true;
		for(int j=0;ok&&j<n;++j)
		{
			if(!vis[j]&&c[j]!=-1)
				ok = ok&&dfs(j), tmp *= 2;
			else if(c[j]==-1)
				for(int x:v[j])
					if(c[x]==-1)
						ok = false;
		}
		if(ok)
			ans += tmp;	
	}
	cout<<ans<<endl;
	return 0;
}