该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给你一个由 $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$ /th 边所连接的顶点。对于每一对顶点 $(u, v)$ ， $u$ 和 $v$ 之间最多有一条边。没有从顶点到自身的边。因此，图中不存在自循环和多条边。该图是非定向，即所有边都是双向的。图是连通的，即沿着图的边移动，可以从任何其他顶点到达任何顶点。

保证 $n$ 的总和不超过 $2 \cdot 10^5$ ( $\sum n \le 2 \cdot 10^5$ )。

输出格式

输出

对于每个测试用例，打印一个整数：给定图形中长度至少*** $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

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]$ .