P40084

counting stars

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

题目描述

给定一张有 n个点和m条边的无向图,求下面图形的出现次数.

输入

输入一个整数T表示样例总数

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

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

输出

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

样例

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

提示

2 \le n \le 10^5 , 1 \le m \le min { 2 \times 10^5,\dfrac{n(n-1)}{2} }

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