実行時間制限: 2 sec / メモリ制限: 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