AT_abc262_b [ABC262B] Triangle (Easier)

题目描述

给定一个有 $N$ 个顶点 $M$ 条边的简单无向图。顶点编号为 $1,\dots,N$，第 $i$ 条边连接顶点 $U_i$ 和顶点 $V_i$。

请计算满足以下所有条件的整数三元组 $a,b,c$ 的总数：

• $1 \leq a < b < c \leq N$。
• 存在一条边连接顶点 $a$ 和顶点 $b$。
• 存在一条边连接顶点 $b$ 和顶点 $c$。
• 存在一条边连接顶点 $c$ 和顶点 $a$。

输入格式

输入按以下格式从标准输入读入。

$N$ $M$
$U_1$ $V_1$
$\vdots$
$U_M$ $V_M$

输出格式

输出答案。

输入输出样例 #1

输入 #1

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

输出 #1

2

输入输出样例 #2

输入 #2

3 1
1 2

输出 #2

0

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $3 \leq N \leq 100$
• $1 \leq M \leq \frac{N(N-1)}{2}$
• $1 \leq U_i < V_i \leq N \quad (1 \leq i \leq M)$
• $(U_i, V_i) \neq (U_j, V_j) \quad (i \neq j)$
• 输入均为整数

样例解释 1

$(a, b, c) = (1, 4, 5),\ (2, 3, 5)$ 满足条件。

由 ChatGPT 4.1 翻译