在去取 Lalo 的保释金时，Saul 和 Mike 在沙漠中迷路了。在沙漠中，他们发现了一个仙人掌图（cactus）：一个包含 $n$ 个节点的连通无向图，其中每条边最多出现在一个简单环中。

已知 $n$ 是偶数。出于某种原因，Mike 和 Saul 想要解决以下问题：

定义 $d(u, v)$ 为该仙人掌图中节点 $u$ 和 $v$ 之间的最短距离。将所有 $n$ 个节点划分为 $\frac{n}{2}$ 个点对 $(u_i, v_i)$，使得每个节点恰好出现在一个点对中，并使 $\sum d(u_i, v_i)$ 最大化。

这种划分下 $d(u_i, v_i)$ 之和的最大可能值是多少？

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n, m$ ($2 \le n \le 2 \cdot 10^5, n - 1 \le m \le 4 \cdot 10^5, n$ 为偶数)，分别表示节点数和边数。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，表示节点 $u_i$ 和 $v_i$ 之间的一条边。保证这些边构成一个仙人掌图。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$，且所有测试用例中 $m$ 的总和不超过 $4 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示该划分下 $d(u_i, v_i)$ 之和的最大可能值。

样例

输入 1

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

输出 1

4
7
11