1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#pragma GCC optimize ("Ofast")
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define FORD(i, a, b) for (int i=(a); i>(b); i--)
#define PPC(x) __builtin_popcount(x)
#define MSB(x) (63 - __builtin_clzll(x))
#define SZ(x) ((int)(x).size())
#define HASK(S, x) (S.find(x) != S.end())
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define ithBit(m, i) ((m) >> (i) & 1)
#define ft first
#define sd second
#define kw(a) ((a) * (a))
#ifdef DEBUG
#include "debug.h"
#else
#define dbg(...) 0
#endif
using namespace std; 

template <typename T1, typename T2> inline void remin(T1& a, T2 b) { a = min(a, (T1)b);	}
template <typename T1, typename T2> inline void remax(T1& a, T2 b) { a = max(a, (T1)b);	}

const int maxN = 1 << 19;

pair <int, int> E[maxN];
vector <int> G[maxN];
int low[maxN], in[maxN], vis[maxN], inCtr, visCtr, bCtr;
bool bed[maxN];

int oth(int e, int v)
{	return E[e].ft ^ E[e].sd ^ v;	}

void dfs(int v, int fet=-1)
{
	in[v] = low[v] = ++inCtr;
	vis[v] = visCtr;
	for (int e : G[v]) if (e != fet and !bed[e])
	{
		int u = oth(e, v);
		if (vis[u] != visCtr)
		{
			dfs(u, e);
			remin(low[v], low[u]);
		}
		else remin(low[v], in[u]);
	}
	
	if (fet != -1 and low[v] == in[v])
		bCtr++;
}

void solve()
{
	int n, m;
	scanf ("%d%d", &n, &m);
	FOR(i, 0, m)
	{
		int a, b;
		scanf ("%d%d", &a, &b);
		E[i] = {a, b};
		G[a].pb(i);
		G[b].pb(i);		
	}

	long long res = 0;

	FOR(i, 1, m) FOR(j, 0, i)
	{
		inCtr = bCtr = 0;
		bed[i] = bed[j] = true;
		visCtr++;
		int compCtr = 0; 
		FOR(v, 1, n+1)
			if (vis[v] != visCtr)
				dfs(v), compCtr++;
		res += compCtr == 1 ? bCtr : m-2;
		bed[i] = bed[j] = false;
	}
	
	printf("%lld\n", res / 3);
}
 
int main()
{
	int t = 1;
	//scanf ("%d", &t);
	FOR(tid, 1, t+1)
	{
		//printf("Case #%d: ", tid);
		solve();
	}
	return 0;
}