给您一个由 $$$n$$$ 个顶点和 $$$n$$$ 边组成的无向图。保证给定的图是连通的(即可以从任何其他顶点到达任何顶点)并且图中不存在自环和多条边。
您的任务是计算给定图中长度至少为 $$$1$$$ 的简单路径的数量。请注意,仅方向不同的路径被视为相同(即您必须计算无向路径的数量)。例如,路径 $$$[1, 2, 3]$$$ 和 $$$[3, 2, 1]$$$ 被视为相同。
您必须回答 $$$t$$$ 独立测试用例。
回想一下,图中的路径是顶点 $$$v_1, v_2, \ldots, v_k$$$ 的序列,使得该序列中的每对相邻(连续)顶点由一条边连接。路径的长度是其中的边数。简单路径是其中所有顶点都不同的路径。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — 图中的顶点数(和边数)。
测试用例的接下来 $$$n$$$ 行描述边:边 $$$i$$$ 被指定为一对顶点 $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$),其中 $$$u_i$$$ 和$$$v_i$$$ 是第 $$$i$$$ 条边连接的顶点。对于每一对顶点 $$$(u, v)$$$,$$$u$$$ 和 $$$v$$$ 之间至多有一条边。从顶点到自身没有边。因此,图中不存在自环和重边。该图是无向的,i。 e.它的所有边缘都是双向的。该图是连通的,i。 e.通过沿着图的边移动,可以从任何其他顶点到达任何顶点。
保证$$$n$$$之和不超过$$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$)。
输出
对于每个测试用例,打印一个整数:给定图中长度至少为 $$$1$$$ 的简单路径的数量。请注意,仅方向不同的路径被视为相同(即您必须计算无向路径的数量)。
示例
输入 #1
3 3 1 2 2 3 1 3 4 1 2 2 3 3 4 4 2 5 1 2 2 3 1 3 2 5 4 3
输出 #1
6 11 18
注意
考虑示例的第二个测试用例。看起来像这样:
有 $$$11$$$ 不同的简单路径:
1. $$$[1, 2]$$$;
2. $$$[2, 3]$$$;
3. $$$[3, 4]$$$;
4. $$$[2, 4]$$$;
5. $$$[1, 2, 4]$$$;
6. $$$[1, 2, 3]$$$;
7. $$$[2, 3, 4]$$$;
8. $$$[2, 4, 3]$$$;
9. $$$[3, 2, 4]$$$;
10. $$$[1, 2, 3, 4]$$$;
11. $$$[1, 2, 4, 3]$$$.