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
#include <bits/stdc++.h>
using namespace std;

typedef long long int LL;

const int MAXN = 200005;
const int MAXE = 500005;

unordered_set<int> blocked_edges;
int n, m;
vector<pair<int,int>> adj[MAXN];
vector<pair<int,int>> edges;
bool visited[MAXN];
bool bridge[MAXE];
int low[MAXN], dist[MAXN], parent[MAXN], cnt_visited;

void dfs(int u) {
  visited[u] = true;
  low[u] = dist[u];
  cnt_visited++;

  unordered_map<int,int> cnt_edges;
  vector<bool> dfs_edges(adj[u].size(), false);

  for (int i = 0; i < adj[u].size(); i++) {
    const auto& e = adj[u][i];
    int v = e.first;
    int eid = e.second;
    if (v == parent[u]) continue;
    if (blocked_edges.count(eid)) continue;

    cnt_edges[v]++;

    if (!visited[v]) {
      dist[v] = dist[u] + 1;
      parent[v] = u;
      dfs(v);
      low[u] = min(low[u], low[v]);
      dfs_edges[i] = true;
    }
    else
      low[u] = min(low[u], dist[v]);
  }

  for (int i = 0; i < adj[u].size(); i++) {
    if (!dfs_edges[i]) continue;
    const auto& e = adj[u][i];
    int v = e.first;
    int eid = e.second;
    if ((cnt_edges[v] == 1) && (low[v] == dist[v])) bridge[eid] = true;
  }
}

int run_low(int min_eid) {
  fill(visited, visited+n, false);
  fill(bridge, bridge+m, false);
  cnt_visited = 0;
  dist[0] = 0;
  parent[0] = -1;
  dfs(0);
  if (cnt_visited < n) return m - min_eid;
  int r = 0;
  for (int eid = min_eid; eid < m; eid++) if (bridge[eid]) r++;
  return r;
}



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

  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--; v--;
    adj[u].push_back(make_pair(v, i));
    adj[v].push_back(make_pair(u, i));
    edges.push_back(make_pair(u, v));
  }

  LL result = 0;
  for (int i = 0; i < m; i++) {
    blocked_edges.insert(i);
    for (int j = i+1; j < m; j++) {
      blocked_edges.insert(j);
      result += run_low(j+1);
      blocked_edges.erase(j);
    }
    blocked_edges.erase(i);
  }

  cout << result << "\n";

  return 0;
}