#include <iostream>
#include <array>
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std;
using lint = long long;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; ++i)
    {
        int s, t;
        cin >> s >> t;
        s--;
        t--;
        g[s].push_back(t);
        g[t].push_back(s);
    }
    vector<int> idx(n, -1); //dfs順を記録。違う連結成分になら同じindexを持ちうる。
    auto dfs = [&](auto dfs, int now, array<int, 20> &v) -> lint {
        for (int to : g[now])
        {
            if (v[to] == v[now])
            {
                return 0;
            }
        }
        lint res = 1;
        for (int to : g[now])
        {
            if (idx[to] == -1)
                idx[to] = idx[now] + 1;
            if (idx[to] == idx[now] + 1)
            {
                lint tmp = 0;
                v[to] = (v[now] + 1) % 3;
                tmp += dfs(dfs, to, v);
                v[to] = (v[now] + 2) % 3;
                tmp += dfs(dfs, to, v);
                v[to] = -1;
                res *= tmp;
                if (tmp == 0)
                    break;
                // tmp == 0 の時、早期に return してるのでidxが振り切れていない事に注意
            }
        }
        return res;
    };

    lint ans = 1;
    array<int, 20> v;
    v.fill(-1);

    for (int i = 0; i < n; ++i)
    {
        if (idx[i] != -1)
            continue;
        idx[i] = 0;
        v[i] = 0;
        ans *= dfs(dfs, i, v) * 3;
    }
    cout << ans << endl;
}
#include <bits/stdc++.h>
 
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<pair<int,int>> vpi;
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define pi pair<int, int>
#define mp make_pair
#define F first
#define S second

int n, m, a, b;
vector<vi> adj;
vi c, cgroup;
vector<bool> vis;


ll calc(int i) {
    if (i==cgroup.size()) return 1;
    int node = cgroup[i];
    ll ans = 0;
    vector<bool> taken(4, false);
    for (int nb : adj[node]) taken[c[nb]]=true;
    F0R(j, 3) if (!taken[j]) {
        c[node]=j;
        ans += calc(i+1);
    }
    c[node]=3;
    return ans;
}

void group(int i) {
    if (vis[i]) return;
    vis[i]=true;
    cgroup.pb(i);
    for (int nb : adj[i]) if (! vis[nb]) group(nb);
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    adj.rsz(n);
    F0R(i, m) {
        cin >> a >> b;
        adj[a-1].pb(b-1);
        adj[b-1].pb(a-1);
    }
    c.rsz(n, 3);
    ll ans = 1;
    vis.rsz(n, false);
    F0R(i, n) {
        if (!vis[i]) {
            cgroup.clear();
            group(i);
            c[i]=0;
            ans *= 3*calc(1);
        }
    }
    cout << ans << '\n';
}
