//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#include <bits/stdc++.h>
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<typename T>
bool umin(T &a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool umax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
#ifdef KIVI
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif
const int max_n = (1e5 + 11) * 4, inf = 1000111222;
vector <int> edge[max_n];
int tin[max_n], tout[max_n], used[max_n], timer = 0, art[max_n], id[max_n], good[max_n];
vector <int> q, current;
vector <vector <int> > cmp;
inline void dfs (int v, int p = -1) {
used[v] = 1;
tin[v] = timer++;
current.pb(v);
tout[v] = tin[v];
q.pb(v);
for (int to : edge[v]) {
if (to == p) {
continue;
}
if (used[to]) {
umin(tout[v], tin[to]);
}
else {
dfs(to, v);
umin(tout[v], tout[to]);
if (tout[to] >= tin[v]) {
art[v] = tin[v] > 0 || tin[to] > 1;
cmp.pb(vector <int>{v});
while (cmp.back().back() != to) {
cmp.back().pb(q.back());
q.pop_back();
}
}
}
}
}
vector <int> e[max_n];
int sz[max_n], n, save[max_n];
ll res[max_n];
ll ans = 0;
inline ll sqr (ll x) {
return x * x;
}
inline void calc (int v, int p = -1) {
// LOG(v, len(e[v]), sz[v], good[v]);
ll cur = sz[v];
save[v] = sz[v];
for (int to : e[v]) {
if (to == p) {
continue;
}
calc(to, v);
sz[v] += sz[to];
}
if (good[v]) {
ans += cur * (cur - 1ll) * (len(current) - cur - len(e[v])) * 2ll; // 2 bad
// LOG(cur * (cur - 1ll) * (len(current) - cur - len(e[v])) * 2ll);
// if (p != -1) {
// ans += cur * 2ll * (len(current) - sz[v] - 1);
// LOG(cur * 2ll * (len(current) - sz[v] - 1));
// }
// for (int to : e[v]) {
// if (to == p) {
// continue;
// }
// ans += cur * 2ll * (sz[to] - 1ll);
// LOG(cur * 2ll * (sz[to] - 1ll), "here");
// }
if (len(e[v]) >= 2) { // 2 good
if (p != -1) {
ans += (len(e[v]) - 1) * (len(e[v]) - 2ll) * 2ll * (len(current) - sz[v] - 1);
// ans += (len(e[v]) - 1ll) * 2ll * (len(current) - sz[v] - 1);
}
for (int to : e[v]) {
if (to == p) {
continue;
}
ans += (len(e[v]) - 1) * (len(e[v]) - 2ll) * 2ll * (sz[to] - 1ll);
// ans += (len(e[v]) - 1ll) * 2ll * (sz[to] - 1ll);
}
}
ll pref = 0; // 1 bad
for (int to : e[v]) {
ll now = sz[to] - 1;
if (to == p) {
now = len(current) - sz[v] - 1;
}
ans += cur * pref * now * 2ll;
// LOG(cur * pref * now * 2);
pref += now;
}
// 1 good
pref = 0;
for (int to : e[v]) {
ll now = sz[to] - 1;
if (to == p) {
now = len(current) - sz[v] - 1;
}
ans += pref * now * len(e[v]) * 2ll;
pref += now;
}
}
else {
// return;
ll allow = len(current) - 1; // 1 bad 1 good
for (int to : e[v]) {
allow -= len(e[to]) - 1;
}
for (int to : e[v]) {
ll now = save[to];
allow -= now;
ans += now * allow * 2ll;
}
// 1 good
// ll pref = 0;
// for (int to : e[v]) {
// ll now = sz[to] - save[to] - len(e[to]) + 1;
// if (to == p) {
// now = len(current) - sz[v] - save[p] - len(e[p]) + 1;
// }
// ans += now * pref * 2ll;
// pref += now;
// LOG(now, pref);
// }
}
}
int val[max_n], V;
ll dp[max_n], cc[max_n];
inline void go (int v, int p = -1) {
cc[v] = sz[v];
dp[v] = 0;
for (int to : e[v]) {
if (to == p) {
continue;
}
go(to, v);
dp[v] += dp[to];
cc[v] += cc[to];
}
dp[v] += cc[v] * (val[v] - 1ll);
}
inline void go_calc (int v, int p = -1, ll DP = 0, ll ccc = 0) {
ll cur_dp = DP, cur_cc = ccc + sz[v];
for (int to : e[v]) {
if (to == p) {
continue;
}
cur_dp += dp[to];
cur_cc += cc[to];
}
ans += (cur_dp + (val[v] - 1ll) * (cur_cc - sz[v]) - (len(current) - sz[v])) * sz[v];
// LOG(v, (cur_dp + (val[v] - 1ll) * (cc[v] - sz[v]) - (len(current) - sz[v])), DP, ccc);
// cur_dp += (val[v] - 1ll) * cur_cc;
for (int to : e[v]) {
if (to == p) {
continue;
}
ll now_dp = cur_dp - dp[to];
ll now_cc = cur_cc - cc[to];
now_dp += now_cc * (val[v] - 1ll);
go_calc(to, v, now_dp, now_cc);
}
}
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int m;
cin >> n >> m;
for (int i = 0, a, b; i < m; i++) {
a = i + 1, b = i + 2;
cin >> a >> b;
--a, --b;
edge[a].pb(b);
edge[b].pb(a);
}
int new_id = 0;
for (int ver = 0; ver < n; ver++) {
if (used[ver]) {
continue;
}
timer = 0;
current.clear();
cmp.clear();
q.clear();
dfs(ver);
if (len(current) == 1) {
continue;
}
for (int i : current) {
if (art[i]) {
val[new_id] = 1;
id[i] = new_id++;
LOG(id[i], i);
}
}
LOG(new_id);
for (auto &i : cmp) {
int now = new_id++, cnt = 0;
good[now] = 1;
val[now] = len(i);
LOG(now, len(i));
for (int x : i) {
LOG(art[x], x);
if (art[x]) {
e[id[x]].pb(now);
e[now].pb(id[x]);
// LOG(id[x], now);
}
else {
++cnt;
id[x] = now;
}
}
// ans += len(i) * (len(i) - 1ll) * (len(i) - 2ll);
// for (int x : i) {
// if (art[x]) {
// ans -= cnt * (cnt - 1ll) * 2;
// }
// }
// ans += len(i) * (len(i) - 1ll) * (len(current) - len(i)) * 2ll;
// LOG(len(i));
}
// LOG(new_id);
for (int i : current) {
++sz[id[i]];
}
for (int i : current) {
V = id[i];
// go(id[i]);
ans += (sz[V] - 1ll) * (val[V] - 2);
// ans += (dp[V] - sz[V] * (val[V] - 1ll) - (len(current) - sz[V]));
// LOG(V, (dp[V] - sz[V] * (val[V] - 1ll) - (len(current) - sz[V])));
LOG(ans, i);
}
go(id[current[0]]);
go_calc(id[current[0]]);
// calc(id[ver]);
}
cout << ans << '\n';
}
/*
10 10
6 2
3 8
3 6
7 1
10 7
4 3
5 7
8 6
7 9
3 7
10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
*/
