All Tracks Problem

Quidditch Practice
Tag(s):
No tags
Problem
Editorial
Analytics

Harry is now in his 6th year at Hogwarts. He has been made the captain of the Gryffindor Quidditch team by Headmaster Dumbledore. Its time for Quidditch practice. So all players must be divided into two teams for practice sessions. Now the problem that he faces before selecting the team is that some players don't feel comfortable playing on the same team as some other players. Harry knows about these restrictions that he has while forming the teams. He wonders if he can make two teams taking into account these restrictions and further how many different teams he can make. But since Harry has detention from Professor Snape, he leaves the task to you.

Calculate the total number of different possible team distributions for Harry. Output the answer modulo (10^9)+7.

Note

The two teams must not necessarily have equal number of players i.e. there can be 3 players on one team and only 1 player on other team. But there has to be atleast one player in each team.

Input

The first line of each test file contains a single integer T. Then T test cases follow. Each line contains two integers N - the number of players and M - the number of different restrictions that Harry must take care of. The next M line each contain two integers A and B, which indicate that player A would not like to play with player B and vice versa.

Output

For each test case output the number of different possible team formations modulo (10^9)+7. If no such formation is possible, output "NOT POSSIBLE" (quotes for clarity only). Each output must be followed by a newline.

Constraints

1<= T <=100

2<= N <= 10^4

0<= M <= 10^5

0<= A,B <=N-1

Problem Setter: Jayam Modi

SAMPLE INPUT
2
10 5
0 4
1 2
1 3
4 8
2 5
10 5
1 2
1 3
2 3
4 7
6 8
SAMPLE OUTPUT
16
NOT POSSIBLE
Explanation

In the second test case, 1 and 2 dont like to play together. Similarly 2 and 3 dont like to play together. So now 1 and 2+3 should be in different teams. But now if 2 and 3 also dont like to play together then there is no possilble team formation.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

NIT Surat

Challenge Name

Epiphany 3.3

Notifications
View All Notifications