Xsquare has recently started an organisation named HackerEarth. Xsquare has hired N employees having employee ID numbered from 1 to N to work within the organisation. Organisational structure is divided into a number of departments. Each of the N employee is hired to work under exactly one department. All the employees working under the same department are somehow related to each other.
More specifically, organisational structure is represented in the form of a forest containing one or more connected components, where each connected component represents a department and contains the IDs of employees working in that department. A department can be represented in the form of a tree.
Look at the following example for better understanding:
Departments :
- employees with ID number {1,3,5,8} work in the same department.
- employees with ID number {4,6,7,10} work in the same department.
- employees with ID number {2,9,11} work in the same department.
As it is just starting days of the organisation, Xsquare decided to maintain the minimum management level within the organisation. For the purpose to be served, Xsquare has decided to select exactly one employee from each department who will be the manager of that particular department. The Manager would thus form the root of the tree representing the department from which he got selected.
Terminologies Involved :
Xsquare is busy managing resources for his organisation. Therefore, he cannot participate in the electing the manager for each department.
Can you help him in accomplishing this task ?
Your task is very simple. You have to count the number of ways of selecting manager from each department such that the management level of his organisation is minimum. Since the answer can be large, output it modulo ( 109 + 7 ).
Input :
First line of input contains a single integer T denoting the number of test cases. First line of each test case contains two space separated N and M denoting the number of employees and number of edges in the tree. Next M lines of each test case contains two space separated integers U and V denoting the employees that are related to each other in some or the other way.
Output :
For each test case, print out the required answer in a separate line.
Constraints :
- 1 ≤ T ≤ 105
- 1 ≤ M < N ≤ 5*105
- 1 ≤ U , V ≤ N
- sum of N over all test cases does not exceed 5*105.
- It is guarantee that given graph is a forest.
Subtasks :
- Subtask 1 : sum of N over all test cases does not exceed 5*103 : ( 25 pts )
- Subtask 2 : sum of N over all test cases does not exceed 5*105 : ( 75 pts )
Warning :
Prefer to use printf / scanf instead of cin / cout.
Sample test case has the same organisational structure as presented in the above figure. Minimum possible management level within the organisation is 2. {1,4,11} {1,4,2} {1,4,9} {1,6,11} {1,6,2} {1,6,9} Here are some possible ways to select the managers from each of the three departments such that management level of the organisation is minimum i.e 2.
