#P18353. Ineffable Cycle
Ineffable Cycle
Ineffable Cycle
输入:标准输入
输出:标准输出
题目描述
给定一个有 个顶点、 条边的简单无向图,顶点编号为 。图中没有自环或重边,图不一定连通。
选择两个不同的顶点 ,满足 ,删除这两个顶点及所有与它们关联的边。求有多少种选择,使剩余图中没有任何环。
没有环的图称为森林;剩余图可以不连通,也可以含有孤立点。每个无序顶点对只计一次。
输入格式
第一行包含一个整数 ,表示测试用例数。
每个测试用例的第一行包含两个整数 。
接下来 行,每行包含两个整数 ,表示顶点 与 之间有一条无向边。
输出格式
对于每个测试用例,输出一行一个整数,表示满足条件的无序顶点对数量。
数据范围
- ;
- ;
- ;
- ,;
- 保证没有重边;
- 同一输入文件中,所有测试用例的 之和不超过 , 之和也不超过 。
答案可能超过 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