Exclusive Cities

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.
Input
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.
Output
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.
Constraints
T <= 10 1 <= n <= 500 0 <= m <= n(n1)/2
Example
Input: 2 3 0 4 1 1 3 Output: 3 2
Explanation:
For the second test case, the pairs of cities that are exclusive are (1,3) and (0,2). So a total of 2 pairs.
Author:  the123abhishek 
Tags  the123abhishek 
Date Added:  17032012 
Time Limit:  0.17341 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, GO 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions