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

题目描述

遥远的 P 国共有 $n$ 个城市，编号为 $1\sim n$。

$m$ 条双向高速公路连接了部分城市。从高速公路的一端所在城市到达另一端所在城市，不需要花费任何代价。相反，若两城市之间未修建高速公路，则需要花费 $1$ 的代价，才能到达另一个城市。

勤劳的 P 国国王 $\text{Setsuna}$ 每 $10^{18}$ 天就要从城市 $1$ 出发，走访所有 $n$ 个城市，询问每个城市的发展情况。

尽管 $\text{Setsuna}$ 总会选择总代价最少的走访方案，但依然不满于路途花费的过多代价。$\text{Setsuna}$ 希望新修建 一条 高速公路，减少走访过程中花费的总代价。然而，复杂的城市道路图实在难以厘清，于是找到了精通算法的你，希望你回答：

• 有多少种新修建 一条 高速公路的方案$^\dagger$，使得走访过程中花费的总代价 减少 ？

$^\dagger$ 称两种修建方法不同，当且仅当它们对应的道路 $(u_1,v_1)$ 和 $(u_2,v_2)$ 是不同的无序二元组，例如 $(2,3)$ 和 $(3,4)$ 是两种方案，但 $(2,3)$ 和 $(3,2)$ 属于同一种方案。

输入格式

第一行一个正整数 $T$，表示测试数据组数。

对于每组数据，第一行两个整数 $n,m$，表示城市数量和现有的高速公路数量。

接下来 $m$ 行每行两个整数 $u_i,v_i$，表示一条双向高速公路。

输出格式

对于每组数据输出一个整数，表示使得总代价减少的方案数。

样例输入

3
4 1
1 2
6 6
1 2
1 3
1 4
2 3
2 4
5 6
3 2
1 2
1 3

样例输出

5
8
0

样例解释

对于第一组数据，只有一条高速公路 $(1,2)$，一种可行的走访方案是 $1\to 2\to 3\to 4$，其中 $2\to 3$ 和 $3\to 4$ 均需要花费 $1$ 的代价。

我们可以在新修建高速公路 $(2,3)$，这样，走访的总代价减少了 $1$。

此外，修建 $(1,3)$，$(1,4)$，$(2,4)$，$(3,4)$ 也是可行的。

对于第三组数据，修建前总代价已经达到了 $0$，无法再被减少。

数据范围与约定

对于 $50\%$ 的数据, $2\le n\le 500$。

对于 $100\%$ 的数据, $1\le T\le 10^4,2\le n\le 2\times 10^5, 1\le m\le 3\times 10^5, 1\le u_i,v_i\le n$。

保证图中不存在重边和自环。

所有的测试数据中，$n$ 的总和不超过 $2\times 10^5$，$m$ 的总和不超过 $5\times 10^5$。