P40083

无向图四元环计数

难度 6 级 有向无环图 拓扑排序 图论
讨论 统计 1通过 1提交 100%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

无向图 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。

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

输出

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

样例

样例 1
输入
5 8
1 2
2 3
3 5
5 4
4 2
5 2
1 4
3 4
输出
5

提示

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

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

样例数量不超过300,1 \le u, v \le n,\sum n \le 3 \times 10^5, \sum m \le 6 \times 10^5

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交