#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

typedef vector<int> vi;
typedef vector<ll> vll;

typedef vector<vi> vvi;
typedef vector<vll> vvll;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

typedef vector<pii> vpii;
typedef vector<pll> vpll;

typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define fi first
#define se second

template<class T> bool ckmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
template<class T> bool ckmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}

namespace debug {
    void __print(int x) {cerr << x;}
    void __print(long long x) {cerr << x;}
    void __print(double x) {cerr << x;}
    void __print(long double x) {cerr << x;}
    void __print(char x) {cerr << '\'' << x << '\'';}
    void __print(const string &x) {cerr << '\"' << x << '\"';}
    void __print(bool x) {cerr << (x ? "true" : "false");}

    template<typename T, typename V>
    void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
    template<typename T>
    void __print(const T &x) {int f = 0; cerr << '{'; for(auto z : x) cerr << (f++ ? "," : ""), __print(z); cerr << "}";}
    void _print() {cerr << "]\n";}
    template <typename T, typename... V>
    void _print(T t, V... v) {__print(t); if(sizeof...(v)) cerr << ", "; _print(v...);}

#ifdef ljuba
#define dbg(x...) cerr << "LINE(" << __LINE__ << ") -> " << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
}

using namespace debug;

const char nl = '\n';

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

vi adj[30];
bool marked[30];
vi adj2[30];
int boje[30];

bool moze = 1;

void dfs(int s, int tren = 0) {
    if(!moze) return;
    boje[s] = tren;
    for(auto e : adj2[s]) {
        if(boje[e] == boje[s]) {
            moze = 0;
            return;
        }
        if(boje[e] != -1) continue;
        dfs(e, tren^1);
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        adj[a].pb(b);
        adj[b].pb(a);
    }

    ll ans = 0;

    for(int i = 0; i < n; ++i) boje[i] = -1;

    for(int mask = 0; mask < (1<<n); ++mask) {
        for(int i = 0; i < n; ++i) {
            marked[i] = (mask>>i)&1;
        }

        bool isti = 0;

        for(int i = 0; i < n; ++i) {
            for(auto e : adj[i]) {
                if(marked[e] && marked[i]) {
                     isti = 1;
                     break;
                }
            }
            if(isti) break;
        }

        if(isti) continue;

        for(int i = 0; i < n; ++i) {
            if(marked[i]) continue;
            for(auto e : adj[i]) {
                if(!marked[e]) adj2[i].pb(e);
            }
        }

        int komp = 0;
        moze = 1;

        for(int i = 0; i < n; ++i) {
            if(marked[i]) continue;
            if(boje[i] == -1) {
                ++komp;
                dfs(i);
                if(!moze) {
                    break;
                }
            }
        }

        if(moze) {
            ll tren = 1;
            for(int i = 0; i < komp; ++i) tren *= 2;
            ans += tren;
            //dbg(mask, komp, tren);
        }

        for(int i = 0; i < n; ++i) {
            adj2[i].clear();
            boje[i] = -1;
        }
    }

    cout << ans << nl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int testCases = 1;
    //cin >> testCases;
    while(testCases--)
        solve();

}

#include<bits/stdc++.h>
using namespace std;
using lli = long long;
#define rep(i,n) for(int i=0;i<n;i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class T>
ostream &operator<<(ostream &os, const vector<T> &x){
    os << "{";
    for(size_t i = 0; i < x.size(); i++){
        if(i < x.size()-1) os << x[i] << ", ";
        else os << x[i];
    }
    os << "}";
    return os;
}

int main(void){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    rep(j, m){
        int s, t;
        cin >> s >> t;
        s--, t--;
        g[s].push_back(t);
        g[t].push_back(s);
    }
    vector<int> idx(n, -1);
    auto dfs = [&](auto dfs, int now, array<int, 20> &v)->lli{
        for(auto to : g[now]){
            if(v[to] == v[now]){
                return 0;
            }
        }
        lli res = 1;
        for(auto to : g[now]){
            if(idx[to] == -1) idx[to] = idx[now]+1;
            if(idx[to] == idx[now]+1){
                lli 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;
            }
        }
        return res;
    };
    lli ans = 1;
    array<int, 20> v;
    v.fill(-1);
    rep(i, n){
        if(idx[i] != -1) continue;
        idx[i] = 0;
        v[i] = 0;
        ans *= dfs(dfs, i, v)*3;
    }
    cout << ans << endl;
    return 0;
}
