All submissions for this problem are available.
Vicky plans to visit Vickyland. Vickyland is a strange state where a city can be connected either by roads to one or more cities(including itself) or can be completely isolated from other cities. While examining the map of Vickyland a very strange and interesting idea came to his mind. He defines 2 cities A and B to form an exclusive pair of cities if and only if for every other vertex C, either A and B both are connected to C or none of them are connected to C. By connected Vicky means that two cities a and b are connected if there exist a sequence of roads from a to b. Now Vicky hopes to determine the number of pairs of exclusive cities in Vickyland. Help him calculate the number of such pairs mod 10^9 + 7.
The first line consists of the number of test cases T, followed by a blank line followed by T test cases. Each test case is separated from the previous one by a blank line.
The first line of each test case contains two space separated integers, n – the number of cities in Vickyland and m – the number of roads in Vickyland. Next follows m lines, the ith of these lines containing two space separated integers xi and yi, specifying that the ith road connects xi to yi. The cities are numbered from 0 to (n – 1).
It is guaranteed that each unordered pair of cities (xi, yi) occurs no more than once.
For each test case print the single integer - the number of unordered pairs of cities that are exclusive mod 10^9 + 7, on a separate line.
T <= 10 1 <= n <= 500 0 <= m <= n(n-1)/2
Input: 2 3 0 4 1 1 3 Output: 3 2
For the second test case, the pairs of cities that are exclusive are (1,3) and (0,2). So a total of 2 pairs.
|Time Limit:||0.17341 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.6, GO|
Fetching successful submissions