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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
// O(m^3)
#include <bits/stdc++.h>
using std::vector;

void init_io() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}

struct Vertex;

struct Edge {
  Vertex *dest;
  size_t edge_idx;
  bool on = true;
};

struct Vertex {
  vector<Edge> edges;
  int depth = -1;
  int low = -1;
};

vector<Vertex> vertices;
vector<std::array<std::pair<Vertex*, size_t>, 2>> edge_ptrs;

void read_input() {
  size_t num_vertices, num_edges;
  std::cin >> num_vertices >> num_edges;
  vertices.resize(num_vertices);
  edge_ptrs.reserve(num_edges);
  for (size_t edge_idx=0; edge_idx<num_edges; ++edge_idx) {
    size_t a, b;
    std::cin >> a >> b;
    --a; --b;
    Vertex *va = &vertices[a];
    Vertex *vb = &vertices[b];
    std::array<std::pair<Vertex*, size_t>, 2> ep;
    for (int i=0; i<2; ++i) {
      Edge edge;
      edge.dest = vb;
      edge.edge_idx = edge_idx;
      ep[i].first = va;
      ep[i].second = va->edges.size();
      va->edges.push_back(edge);
      std::swap(a, b);
      std::swap(va, vb);
    }
    edge_ptrs.push_back(ep);
  }
}

void set_edge_on(const size_t edge_idx, bool on) {
  for (const auto [v, i] : edge_ptrs[edge_idx]) {
    v->edges[i].on = on;
  }
}

size_t g_min_bridge_idx;
size_t g_visited_vertices;
size_t g_num_bridges;

void biconnected_components(Vertex *v, size_t parent_edge, int depth) {
  ++g_visited_vertices;
  v->depth = depth;
  v->low = depth;
  for (const Edge &edge : v->edges) {
    if (edge.edge_idx == parent_edge || !edge.on) continue;
    Vertex *w = edge.dest;
    const int d = w->depth;
    if (d == -1) {
      biconnected_components(w, edge.edge_idx, depth+1);
      if (w->low >= depth+1) {
        g_num_bridges += edge.edge_idx >= g_min_bridge_idx;
      } else {
        v->low = std::min(v->low, w->low);
      }
    } else {
      v->low = std::min(v->low, d);
    }
  }
}

size_t count_disconnecting_edges(size_t min_bridge_idx) {
  for (Vertex &v : vertices) {
    v.depth = -1;
    v.low = -1;
  }
  g_min_bridge_idx = min_bridge_idx;
  g_visited_vertices = 0;
  g_num_bridges = 0;
  biconnected_components(&vertices[0], edge_ptrs.size(), 0);
  if (g_visited_vertices == vertices.size()) {
    return g_num_bridges;
  } else {
    return edge_ptrs.size() - g_min_bridge_idx;
  }
}

uint64_t solve() {
  uint64_t res = 0;
  for (size_t edge0 = 0; edge0 < edge_ptrs.size(); ++edge0) {
    set_edge_on(edge0, false);
    for (size_t edge1 = edge0+1; edge1 < edge_ptrs.size(); ++edge1) {
      set_edge_on(edge1, false);
      const auto c = count_disconnecting_edges(edge1+1);
      set_edge_on(edge1, true);
      res += c;
    }
    set_edge_on(edge0, true);
  }
  return res;
}

int main() {
  init_io();
  read_input();
  const auto res = solve();
  std::cout << res << "\n";
}