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
 97
 98
 99
100
101
102
103
104
#include "bits/stdc++.h" // Tomasz Nowak
using namespace std;     // XIII LO Szczecin
using LL = long long;    // Poland
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
template<class T> int size(T &&x) {
	return int(x.size());
}
template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) {
	out << '{';
	for(auto it = x.begin(); it != x.end(); ++it)
		out << *it << (it == prev(x.end()) ? "" : ", ");
	return out << '}';
}
void dump() {}
template<class T, class... Args> void dump(T &&x, Args... args) {
	cerr << x << ";  ";
	dump(args...);
}
#ifdef DEBUG
  struct Nl{~Nl(){cerr << '\n';}};
# define debug(x...) cerr << (strcmp(#x, "") ? #x ":  " : ""), dump(x), Nl(), cerr << ""
#else
# define debug(...) 0 && cerr
#endif
mt19937_64 rng(0);
int rd(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}
// end of templates

vector<pair<int, int>> edges;
vector<vector<int>> graph;
vector<bool> blocked_edge;

int to(int v, int e) {
	return edges[e].first ^ edges[e].second ^ v;
}

vector<int> pre, low;
vector<int> parent_edge;
int gtime = 0;

void dfs(int v, int par_edge = -1) {
	pre[v] = low[v] = gtime++;
	parent_edge[v] = par_edge;
	for(int e : graph[v])
		if(not blocked_edge[e] and e != par_edge) {
			int u = to(v, e);
			if(pre[u] == -1) {
				dfs(u, e);
				low[v] = min(low[v], low[u]);
			}
			else if(pre[u] < pre[v])
				low[v] = min(low[v], pre[u]);
		}
}

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

	int n, m;
	cin >> n >> m;
	edges.resize(m);
	graph.resize(n);
	REP(i, m) {
		auto &[v, u] = edges[i];
		cin >> v >> u;
		--v, --u;
		graph[v].emplace_back(i);
		graph[u].emplace_back(i);
	}

	LL ans = 0;
	REP(e1, m)
		REP(e2, e1) {
			pre.assign(n, -1);
			gtime = 0;
			low = pre;
			blocked_edge.assign(m, false);
			blocked_edge[e1] = blocked_edge[e2] = true;
			parent_edge.assign(n, -1);
			dfs(0);
			// debug(e1, e2, pre, low, parent_edge);
			if(*min_element(pre.begin(), pre.end()) == -1) {
				ans += m - 2;
				continue;
			}
			int bridges = 0;
			REP(v, n)
				if(parent_edge[v] != -1) {
					int u = to(v, parent_edge[v]);
					if(pre[u] < low[v])
						++bridges;
				}
			debug(e1, e2, bridges);
			ans += bridges;
		}
	cout << (ans / 3) << '\n';
}