191 无向图四元环计数

内存限制:512 MB 时间限制:1000 ms

题目描述

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

输出格式

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

样例

数据范围与提示

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

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

样例

样例输入 1

4 4 1 2 2 3 3 4 4 1

样例输出 1

1

样例输入 2

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

样例输出 2

5