SOLVE

LATER

Quidditch Practice

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

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++,
C++14,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Julia,
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Swift,
Visual Basic,
Kotlin

Initializing Code Editor...

OTHER PROBLEMS OF THIS CHALLENGE

{"56da88b": "/pagelets/show-submission/algorithm/quidditch-practice-problem/", "56da8f2": "/pagelets/recommended-problems/algorithm/quidditch-practice-problem/", "56da8ac": "/pagelets/suggested-problems/algorithm/quidditch-practice-problem/", "56da8dc": "/pagelets/problems-hint/algorithm/quidditch-practice-problem/", "56da8c3": "/pagelets/problem-author-tester/algorithm/quidditch-practice-problem/"}

{}

realtime.hackerearth.com

80

01cdd57962c31902dcf78221beddf17b2e9399b0

58a29e5cae2309f04b28

/realtime/pusher/auth/