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

#define int long long

#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)

const int maxn = 2e3 + 5;

mt19937 rnd(time(0));

int n, M;
vector<int> e[maxn];

map<int, int> mp;
int dep[maxn], fa[maxn], tf[maxn], b[maxn], m, anc;

inline void dfs(int x){
    dep[x] = dep[fa[x]] + 1;
    for(int v : e[x]) if(!fa[v] and v != anc)
        fa[v] = x, dfs(v);
}

inline void dfs2(int x){
    for(int v : e[x]) if(fa[v] == x)
        dfs2(v), tf[x] ^= tf[v];
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL);

    cin >> n >> M;
    rep(i, 1, M){
        int u, v; cin >> u >> v;
        e[u].push_back(v), e[v].push_back(u);
    }

    rep(i, 1, n) if(!fa[i]) anc = i, dfs(i);

    rep(u, 1, n) for(int v : e[u]) if(dep[v] > dep[u]){
        if(fa[v] == u) continue;
        int x = v; b[++m] = rnd();
        tf[u] ^= b[m], tf[v] ^= b[m];
        // while(x != u) tf[x] ^= b[m], x = fa[x];
    }
    rep(i, 1, n) if(!fa[i]) dfs2(i);
    rep(i, 2, n) b[++m] = tf[i];

    sort(b + 1, b + m + 1);

    // rep(i, 1, m) cout << b[i] << " "; cout << '\n';

    int res = 0;
    rep(i, 1, m) res ^= b[i];

    if(!res) return cout << 1 << '\n', 0;

    for(int l = 1, r; l <= m; l = r + 1){
        r = l;
        while(r < m and b[r + 1] == b[l]) ++r;
        if(b[l]) mp[b[l]] = r - l + 1;
    }
    

    if(mp.find(res) != mp.end()) return cout << mp[res] << '\n', 0;

    int ans = 0;
    for(auto [val, num] : mp) if(mp.find(res ^ val) != mp.end())
        ans += num * mp[res ^ val];
    ans /= 2ll;
    // if(mp.find(res) != mp.end()) ans += mp[res];

    cout << ans << '\n';
    return 0;
}