【题目描述】

​ 小$L$决定去$A$国旅行。$A$国有$n$个景点，有些景点之间有双向道路相连。可以抽象为一个$n$个点$m$条边的简单无向图。保证没有重边和自环。小$L$现在想从某个起点 $s$ 出发，沿着道路走到某个终点 $t$ ($s$和$t$可以相同)。使得有$m-2$条边被经过了$2$次，且有$2$条边被经过了$1$次。现在小$L$想知道要多少种旅行方案，你能帮帮他吗？

​ 注意：两种旅行方案不同当且仅当$2$条被经过$1$次的边不同，跟起点、终点，以及走的顺序无关。

【输入格式】

​ 输入文件名为journey.in。

​ 第一行一个正整数$T$，表示测试点数目。

​ 对于每一个测试点，第一行两个数$n$和$m$，分别表示点数和边数。

​ 接下来$m$行每行两个数$x$,$y$，表示$x$号点和$y$号点之间有一条无向边。

【输出格式】

​ 输出文件名为journey.out。

​ 对于每一个测试点，输出一行一个数，表示旅行方案数。

【样例1】

1
4 3
1 2
1 3
1 4

3

【样例解释】

​ 有三种方案：

​ $2 \rightarrow 1 \rightarrow 4 \rightarrow 1 \rightarrow 3$

​ $2 \rightarrow 1 \rightarrow 3 \rightarrow 1 \rightarrow 4$

​ $3 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 4$

【样例2】

​ 见下发文件。

【数据范围】

​ 对于 $30\%$的数据，满足 $n \leq 5$。

​ 对于 $50\%$ 的数据，满足$n \leq 1000$。

​ 另有 $10\%$ 的数据，满足图是一条链。

​ 另有 $20\%$ 的数据，满足图是一棵树。

​ 对于 $100\%$ 的数据，满足 $1 \leq n \leq 100000，2 \leq m \leq 300000,1 \leq T \leq 10$。