In ICPCCamp there were n towns conveniently numbered with 1, 2, . . . , n connected with m roads.
Bobo would like to know the number of ways to keep only (n−1) roads so that the towns remain connected.
Note that the towns are connected if and only any two cities reach each other.

The input contains zero or more test cases and is terminated by end-of-file. For each test case:
The first line contains two integers n and m.
The i-th of the following m lines contains two integers ai and bi which denotes a road between cities a_i and b_i.
• 1 ≤ n≤10⁵
• n < m < n + 100
• 1 ≤ a_i, b_i ≤ n
• The towns are connected with m roads.
• The number of test cases does not exceed 10.

For each test case, output an integer which denotes the number of ways modulo (10⁹ + 7).

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

3
9

2017年四川省赛