SP9916 PONY1 - Help Dr Whooves
题目描述
在小马国大陆上， Dr. Whooves 曾经拥有一切。他拥有一家非常成功的运输公司，与小马国的所有村庄和城镇相连。然而，当无序接管小马国时，很多小马都感到困惑了。即使是现在，他的一些工人仍在错误的路线上工作，而 Dr. Whooves 非常确定他的业务现在已经支离破碎，并且他不再与小马国的所有村庄有联系。
暮光闪闪和她的朋友们随时为您提供帮助。 Dr. Whooves 知道他需要添加最少数量的路线才能确保他的业务重新连接。他让暮光闪闪和她的朋友们找出他可以选择多少种不同的方式来添加这个最少数量的路线，以便他的业务能够连接到小马国的所有城市。可能有很多方法，因此小马们一致同意给出对 $999,999,937$ 取模的答案。
输入格式
首先是一个整数 $T$，即测试用例的数量，后面是每个测试用例的 $T$ 组数据。
每个测试用例的格式如下：
第一行有两个数，分别为 $C,R$，表示单线上有 $C$ 个城市，编号为 $1$ 至 $C$，还有 $R$ 条线路。
之后有 $R$ 行，每行有 $2$ 个数，分别为 $A_i,B_i$，表示城市 $A_i$ 和 $B_i$ 之间的双向路线。
输出格式
共有 $T$ 行，每行有 $1$ 个数，表示 Dr. Whooves 可以选择添加重新连接其业务所需的最小线路数量的不同方式的数量，输出答案求模 $999999937$ 的结果。
## 输入样例
```
4
4 0
3 1
1 2
5 4
1 2
2 3
3 4
2 5
7 6
2 3
3 4
2 4
5 6
6 7
7 5
```
## 输出样例
```
16
2
1
63
```
说明/提示
数据范围：$1 \leq C \leq 10^6,1 \leq C \leq \min(C, 10000)$