All Tracks Problem

Quidditch Practice
No tags

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.


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.


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.


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.


1<= T <=100

2<= N <= 10^4

0<= M <= 10^5

0<= A,B <=N-1

Problem Setter: Jayam Modi

10 5
0 4
1 2
1 3
4 8
2 5
10 5
1 2
1 3
2 3
4 7
6 8

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


Initializing Code Editor...
Your Rating:


This Problem was Asked in

NIT Surat

Challenge Name

Epiphany 3.3

View All Notifications