In ICPCCamp there were n towns conveniently numbered with
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  and  which denotes a road between cities  and .

* 
* n < m < n + 100
* 
* 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 .

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