J - 等距離三角形 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MiB

問題文

N 頂点 M 辺の単純無向グラフが与えられます。
頂点には 1 から N の番号がついており、i 番目の辺は頂点 A_i と頂点 B_i を双方向に結んでいます。

頂点 x と頂点 y が同じ連結成分に属するとき、頂点 x から頂点 y への距離を、頂点 x から頂点 y へのパスに含まれる辺の本数の最小値とします。

以下の条件を全て満たす整数の組 (i,j,k) の個数を求めてください。

  • 1 \leq i < j < k \leq N
  • 頂点 i,j,k は同じ連結成分に属する
  • 「頂点 i から頂点 j への距離」「頂点 j から頂点 k への距離」「頂点 k から頂点 i への距離」の 3 つの値が等しい

制約

  • 3 \leq N \leq 500
  • 0 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq A_i < B_i \leq N
  • (A_i,B_i) は相異なる
  • 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

答えを出力せよ。

入力例 1

5 5
1 2
1 3
1 4
1 5
4 5

出力例 1

3

(1,4,5),(2,3,4),(2,3,5) の 3 組が条件を満たします。

入力例 2

4 2
1 2
3 4

出力例 2

0

Problem Statement

You are given a simple undirected graph with N vertices and M edges.
The vertices are numbered 1 through N, and the i-th edge connects vertices A_i and B_i.

For vertices x and y belonging to the same connected component, define the distance from vertex x to vertex y as the smallest number of edges contained in a path from vertex x to vertex y.

Find the number of triples of integers (i,j,k) such that:

  • 1 \leq i < j < k \leq N,
  • vertices i,j, and k belong to the same connected component, and
  • the following three values are equal: the distance from vertex i to vertex j, the distance from vertex j to vertex k, and the distance from vertex k to vertex i.

Constraints

  • 3 \leq N \leq 500
  • 0 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq A_i < B_i \leq N
  • (A_i,B_i) are pairwise distinct.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

5 5
1 2
1 3
1 4
1 5
4 5

Sample Output 1

3

Three triples (1,4,5),(2,3,4),(2,3,5) satisfy the conditions.

Sample Input 2

4 2
1 2
3 4

Sample Output 2

0