102621: [AtCoder]ABC262 B - Triangle (Easier)

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

问题描述

给你一个包含 N 个顶点和 M 条边的简单无向图。顶点编号为1到N，第i条边（1≤i≤M）连接顶点U_i和顶点V_i。

找出满足以下所有条件的整数元组a, b, c的数量：

• 1≤a
• 存在一条连接顶点a和顶点b的边。
• 存在一条连接顶点b和顶点c的边。
• 存在一条连接顶点c和顶点a的边。

限制条件

• 3≤N≤100
• 1≤M≤N(N-1)/2
• 1≤U_i
• (U_i, V_i)≠(U_j, V_j) (i≠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