20082 - [模板]无向图三元环计数

通过次数

1

提交次数

1

时间限制 : 1 秒
内存限制 : 128 MB

无向图 G 的三元环指的是一个 G 的一个子图 G_0,满足 G_0 有且仅有三个点 u, v, w,有且仅有三条边 \langle u, v \rangle, \langle v, w \rangle, \langle w, u \rangle。两个三元环 G_1, G_2 不同当且仅当存在一个点 u,满足 u \in G_1u \notin G_2

输入

给定一个 n 个点 m 条边的简单无向图,求其三元环个数。

每个测试点有且仅有一组测试数据。

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

2 到第 (m + 1) 行,每行两个用空格隔开的整数 u, v,代表有一条连接节点 u 和节点 v 的边。

输出

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

样例

输入

3 3
1 2
2 3
3 1

输出

1

输入

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

输出

5

提示

样例二解释 共有 5 个三元环,每个三元环包含的点分别是 {1, 2, 4}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}