B - Triangle (Easier) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

N 頂点 M 辺の単純無向グラフが与えられます。頂点には 1, \dots, N の番号が付けられており、i \, (1 \leq i \leq M) 番目の辺は頂点 U_i と頂点 V_i を結んでいます。

以下の条件を全て満たす整数 a, b, c の組の総数を求めてください。

  • 1 \leq a \lt b \lt c \leq N
  • 頂点 a と頂点 b を結ぶ辺が存在する。
  • 頂点 b と頂点 c を結ぶ辺が存在する。
  • 頂点 c と頂点 a を結ぶ辺が存在する。

制約

  • 3 \leq N \leq 100
  • 1 \leq M \leq \frac{N(N - 1)}{2}
  • 1 \leq U_i \lt V_i \leq N \, (1 \leq i \leq M)
  • (U_i, V_i) \neq (U_j, V_j) \, (i \neq j)
  • 入力は全て整数

入力

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

N M
U_1 V_1
\vdots
U_M V_M

出力

答えを出力せよ。

入力例 1

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

出力例 1

2

(a, b, c) = (1, 4, 5), (2, 3, 5) が条件を満たします。

入力例 2

3 1
1 2

出力例 2

0

入力例 3

7 10
1 7
5 7
2 5
3 6
4 7
1 5
2 4
1 3
1 6
2 7

出力例 3

4

Score : 200 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, \dots, N, and the i-th (1 \leq i \leq M) edge connects Vertex U_i and Vertex V_i.

Find the number of tuples of integers a, b, c that satisfy all of the following conditions:

  • 1 \leq a \lt b \lt c \leq N
  • There is an edge connecting Vertex a and Vertex b.
  • There is an edge connecting Vertex b and Vertex c.
  • There is an edge connecting Vertex c and Vertex a.

Constraints

  • 3 \leq N \leq 100
  • 1 \leq M \leq \frac{N(N - 1)}{2}
  • 1 \leq U_i \lt V_i \leq N \, (1 \leq i \leq M)
  • (U_i, V_i) \neq (U_j, V_j) \, (i \neq j)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
U_1 V_1
\vdots
U_M V_M

Output

Print the answer.

Sample Input 1

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

Sample Output 1

2

(a, b, c) = (1, 4, 5), (2, 3, 5) satisfy the conditions.

Sample Input 2

3 1
1 2

Sample Output 2

0

Sample Input 3

7 10
1 7
5 7
2 5
3 6
4 7
1 5
2 4
1 3
1 6
2 7

Sample Output 3

4