All submissions for this problem are available.
A free subtree is defined as a connected subgraph with no cycles.
Given a graph G on N vertices, output the number of free subtrees on N vertices in G.
The first line contains a single integer T, which denotes the number of test cases.
Each test case begins with a line containing two space separated integers N and M, where N and M are the number of vertices and the number of edges, respectively.
The next M lines each contain two space separated integers X and Y, which denotes that there is an edge between vertices X and Y.
A single line per test case containing an integer which denotes the number of free subtrees in the corresponding graph. Since the answer can be very large, output it modulo 109+7.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 100
- 1 ≤ M ≤ N*(N-1)/2
- 0 ≤ X,Y ≤ N-1
Input: 1 5 6 0 1 1 4 3 4 2 3 1 3 0 2 Output: 11
|Time Limit:||0.238213 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, GO|
Fetching successful submissions