主页 讨论版 问题 名次 状态 统计
欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~
问题 A: 大红数星星

问题 A: 大红数星星

时间限制: 3 Sec  内存限制: 128 MB
提交: 1126  解决: 78
[提交][状态][讨论版]

题目描述

“三角形十分的美丽,相信大家小学就学过三角形具有稳定性,三角形也是二维几何中最基本的必不可少的元素之……”,大红走在路上若有所思,突然抬头看到了天空中有很多很亮的星星划过,星星和他们划过的轨迹像极了一个无向图。于是好学的大红,就开始数起了“三角形”,1、2、3……数了好久,大红数的眼泪都掉下来了,所以他哭着请求你来帮他,你这么好心一定不会拒绝吧!大红的三角形的定义:如果存在这样的三个边(A,B)、(B,C)、(A,C)(无向边),则算一个三角形。
大红会告诉你这个图G=(V,E),点数(星星个数)n和边数(轨迹个数)m以及每条边的两个点。

两个三角形不同是:当对于两个三角形的边,某个三角形存在一条边在另一个三角形的边中无法找到!

输入

多组数据。
第一行一个整数T<=10表示数据组数。
对于每组数据的第一行n表示星星个数,m表示星星划过的轨迹的个数,
接下来m行表示每个星星划过的轨迹的端点x,y(1<=x,y<=n)。
1<=n<=100000,1<=m<=min(100000,n*(n-1)/2)

输出

对于每组数据输出一个整数,表示三角形的个数。

样例输入

1
3 3
1 2
2 3
1 3

样例输出

1

提示

保证数据没有重边和自环。

[提交][状态][讨论版]