[AdditionalFile191.zip](file://AdditionalFile191.zip?type=additional_file)

#191. 无向图四元环计数

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB 通过: 440 | 提交: 790

题目描述

无向图 $G$ 的四元环指的是一个 $G$ 的一个子图 $G_0$，满足 $G_0$ 有且仅有四个点 $a,b,c,d$，有且仅有四条边 $\langle a,b \rangle, \langle b,c \rangle, \langle c,d \rangle, \langle d,a \rangle$。两个四元环 $G_1, G_2$ 不同当且仅当存在一条边 $e$，满足 $e \in G_1$ 且 $e \notin G_2$。

给定一个 $n$ 个点 $m$ 条边的简单无向图，不存在重边或自环，求其四元环个数。

输入格式

输入的第一行是用一个空格隔开的两个整数，分别代表图的点数 $n$ 和边数 $m$。

接下来 $m$ 行，每行两个用空格隔开的整数 $u,v$，代表有一条连接节点 $u$ 和节点 $v$ 的边。

输出格式

输出一行一个整数，代表该图的四元环个数。

样例

输入

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

输出

5

数据范围与提示

对于 30% 的数据，保证 $n \le 500$, $m \le 10^3$。

对于 100% 的数据，$1 \le n \le 10^5$, $1 \le m \le 2 \times 10^5$, $1 \le u,v \le n$，给出的图不存在重边和自环，但不保证图连通。