#P18353. Ineffable Cycle

Ineffable Cycle

Ineffable Cycle

输入:标准输入
输出:标准输出

题目描述

给定一个有 nn 个顶点、mm 条边的简单无向图,顶点编号为 1,2,…,n1,2,\ldots,n。图中没有自环或重边,图不一定连通。

选择两个不同的顶点 i,ji,j,满足 1≤i<j≤n1\le i<j\le n,删除这两个顶点及所有与它们关联的边。求有多少种选择,使剩余图中没有任何环。

没有环的图称为森林;剩余图可以不连通,也可以含有孤立点。每个无序顶点对只计一次。

输入格式

第一行包含一个整数 TT,表示测试用例数。

每个测试用例的第一行包含两个整数 n,mn,m。

接下来 mm 行,每行包含两个整数 u,vu,v,表示顶点 uu 与 vv 之间有一条无向边。

输出格式

对于每个测试用例,输出一行一个整数,表示满足条件的无序顶点对数量。

数据范围

  • 1≤T≤2×1051\le T\le 2\times10^5;
  • 3≤n≤5×1053\le n\le 5\times10^5;
  • 0≤m≤min⁡{n(n−1)2,5×105}0\le m\le \min\{\frac{n(n-1)}2,5\times10^5\};
  • 1≤u,v≤n1\le u,v\le n,u≠vu\ne v;
  • 保证没有重边;
  • 同一输入文件中,所有测试用例的 nn 之和不超过 5×1055\times10^5,mm 之和也不超过 5×1055\times10^5。

答案可能超过 32 位有符号整数范围。

样例输入 1

3
7 7
1 2
2 3
3 4
4 5
5 1
4 6
6 7
8 9
1 2
2 3
3 4
1 5
5 6
6 4
1 7
7 8
8 4
7 8
1 2
2 3
3 4
4 1
4 5
5 6
6 7
7 4

样例输出 1

20
25
15