#include <vector>
#include <utility>
#include <map>
#include <set>
#include <random>
#include <algorithm>
#include <cstdio>
using namespace std;
vector <int> T[200007],  Graph[200007];
vector <pair<int, int>> G[200007];
int n, m, bridges, low[200007], pre[200007], post[200007], jump[18][200007], pass[200007];
unsigned long long hasz_node[200007], hasz_edge[500007];
long long ret = 0;
map <unsigned long long, int> active, non_bridge, one_passing;
set <pair<int, int>> in[200007], out[200007];
vector <pair<int, int>> push_hld[200007];
bool vis[200007], is_tree[500007];
pair<int, int> edges[500007];
long long newt2(long long a) {
    return a * (a - 1) / 2;
}

long long newt3(long long a) {
    return a * (a - 1) / 2 * (a - 2) / 3;
}
unsigned long long getLL(unsigned long long a = 0, unsigned long long b = ULLONG_MAX) {
    static mt19937_64 rng(420);
    return uniform_int_distribution <unsigned long long> (a, b)(rng);
}
void dfs(int u, int p) {
    static int time = 0;
    vis[u] = true;
    pre[u] = ++time;
    low[pre[u]] = pre[u];
    for (auto &e : Graph[u]) {
        int v = edges[e].first ^ edges[e].second ^ u;
        if (!vis[v]) {
            is_tree[e] = true;
            dfs(v, e);
            low[pre[u]] = min(low[pre[u]], low[pre[v]]);
            hasz_node[pre[u]] ^= hasz_node[pre[v]];
        } else if (e != p) {
            low[pre[u]] = min(low[pre[u]], pre[v]);
            hasz_node[pre[u]] ^= hasz_edge[e];
        } else
            jump[0][pre[u]] = pre[v];
    }

    post[pre[u]] = time;
}
bool child(int u, int v) {
    return u <= v && post[v] <= post[u];
}
int lca(int u, int v) {
    for (int t = 18 - 1; t >= 0; --t)
        if (!child(jump[t][v], u))
            v = jump[t][v];

    if (!child(v, u))
        v = jump[0][v];

    return v;
}
int get_sub(int p, int c) {
    auto it = upper_bound(T[p].begin(), T[p].end(), c);
    return *--it;
}
long long getBridges() {
    long long ret = bridges * newt2(m - bridges);
    ret += newt2(bridges) * (m - bridges);
    ret += newt3(bridges);
    return ret;
}
void dfs(int u) {
    if (hasz_node[u])
        active[hasz_node[u]]++;

    for (auto v : T[u]) {
        dfs(v);

        if (in[u].size() < in[v].size())
            swap(in[u], in[v]);

        for (auto s : in[v])
            in[u].insert(s);

        in[v].clear();

        if (out[u].size() < out[v].size())
            swap(out[u], out[v]);

        for (auto s : out[v])
            out[u].insert(s);

        out[v].clear();
        pass[u] += pass[v];
    }

    for (auto [v, e] : G[u]) {
        if (v < u) {
            pass[u]++;
            in[u].insert({u, e});
            out[u].insert({v, e});
        } else {
            pass[u]--;
            in[u].erase({v, e});
            out[u].erase({u, e});
        }
    }

    if (pass[u] == 0)
        return;

    active[hasz_node[u]]--;

    if (pass[u] == 1)
        one_passing[hasz_node[u]]++;
    else if (pass[u] == 2)
        ++ret;

    if (pass[u] > 1) {
        int e1 = (*in[u].begin()).second, e2 = (*in[u].rbegin()).second;

        unsigned long long h1 = hasz_node[u] ^ hasz_edge[e1], h2 = hasz_node[u] ^ hasz_edge[e2];

        ret += non_bridge[h1] - active[h1];
        ret += non_bridge[h2] - active[h2];

        int e = (*out[u].rbegin()).second;
        ret += active[hasz_node[u] ^ hasz_edge[e]];
    }

    int a = (*in[u].begin()).first;
    int b = (*in[u].rbegin()).first;
    int t = lca(a, b);

    if (pass[u] > 1 && (*in[u].begin()).first != t) {
        int fa = get_sub(t, a), fb = get_sub(t, b);

        auto it = in[u].lower_bound({fb, 0});
        int m = (*--it).first;

        if (m <= post[fa]) {
            unsigned long long hasza = 0;

            for (const auto &[v, e] : in[u])
                if (v <= m)
                    hasza ^= hasz_edge[e];

            unsigned long long haszb = hasz_node[u] ^ hasza;
            ret += (non_bridge[hasza] - active[hasza]) * (non_bridge[haszb] - active[haszb]);
        }
    }

    for (int s = t; s != u; s = jump[0][s])
        ret += non_bridge[hasz_node[u] ^ hasz_node[s]];
}

main() {
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= m; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        edges[i] = {u, v};
        Graph[u].push_back(i);
        Graph[v].push_back(i);
    }

    for (int i = 1; i <= n; ++i)
        random_shuffle(Graph[i].begin(), Graph[i].end());

    for (int i = 1; i <= m; ++i)
        hasz_edge[i] = getLL();

    dfs(1, -1);

    for (int i = 1; i <= m; ++i) {
        auto &[u, v] = edges[i];

        if (is_tree[i])
            T[min(pre[u], pre[v])].push_back(max(pre[u], pre[v]));
        else {
            G[pre[u]].push_back({pre[v], i});
            G[pre[v]].push_back({pre[u], i});
        }
    }

    for (int i = 2; i <= n; ++i)
        bridges += low[i] == i;

    for (int i = 1; i <= n; ++i) {
        sort(G[i].begin(), G[i].end());
        sort(T[i].begin(), T[i].end());
    }

    jump[0][1] = 1;

    for (int i = 1; i < 18; ++i)
        for (int j = 1; j <= n; ++j)
            jump[i][j] = jump[i - 1][jump[i - 1][j]];

    ret = getBridges();

    for (int i = 2; i <= n; ++i)
        if (low[i] < i)
            non_bridge[hasz_node[i]]++;

    dfs(1);

    for (auto [key, val] : non_bridge) {
        if (one_passing.count(key))
            ret += 1LL * val * (m - bridges - val - 1);

        ret += newt2(val) * (m - bridges - val);
        ret += newt3(val);
    }

    printf("%lld", ret);
}

answer.code:26:75: error: ‘ULLONG_MAX’ was not declared in this scope
   26 | unsigned long long getLL(unsigned long long a = 0, unsigned long long b = ULLONG_MAX) {
      |                                                                           ^~~~~~~~~~
answer.code:8:1: note: ‘ULLONG_MAX’ is defined in header ‘<climits>’; did you forget to ‘#include <climits>’?
    7 | #include <cstdio>
  +++ |+#include <climits>
    8 | using namespace std;
answer.code:159:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
  159 | main() {
      | ^~~~
answer.code: In function ‘int main()’:
answer.code:160:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  160 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
answer.code:164:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  164 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~