### 问题描述 小 $L$ 决定去 $A$ 国旅行。$A$ 国有 $n$ 个景点，有些景点之间有双向道路相连。可以抽象为一个 $n$ 个点 $m$ 条边的简单无向图。保证没有重边和自环。小 $L$ 现在想从某个起点 $s$ 出发，沿着道路走到某个终点 $t$ ($s$ 和 $t$ 可以相同)。使得有 $m-2$ 条边被经过了 $2$ 次，且有 $2$ 条边被经过了 $1$ 次。现在小 $L$ 想知道要多少种旅行方案，你能帮帮他吗？注意：两种旅行方案不同当且仅当 $2$ 条被经过 $1$ 次的边不同，跟起点、终点，以及走的顺序无关。 ### 输入格式 第一行一个正整数 $T$，表示测试点数目。 对于每一个测试点，第一行两个数 $n$ 和 $m$，分别表示点数和边数。 接下来 $m$ 行每行两个数 $x$,$y$，表示 $x$ 号点和 $y$ 号点之间有一条无向边。 ### 输出格式 对于每一个测试点，输出一行一个数，表示旅行方案数。 ### 输入样例 ``` 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$ ### 数据范围 对于 $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$。