All Tracks Data Structures Disjoint Data Structures Basics of Disjoint Data Structures Problem

Teacher's Dilemma
Tag(s):

Disjoint Set, Easy, approved

Problem
Editorial
Analytics

Monk is having a hard time teaching the $$2^{nd}$$ standard students. He wants to divide the students into small groups so that he can conduct some fun-filled activities for them. But students also want their friends in the same group. So, if student $$A$$ is a friend of student $$B$$, and student $$B$$ is a friend of student $$C$$, then the students $$A$$,$$B$$ and $$C$$ must be in the same group, otherwise they will start crying. After dividing the students, he will choose a leader from each group who will lead their respective groups. Now he wants to know the number of ways he can choose the group leaders from all the groups. Print this answer modulo $$10^9+7$$.

Note: Two ways $$A$$ and $$B$$ will be considered different if at least $$1$$ person is a leader in group $$A$$, and is not a leader in group $$B$$, or vice-versa.

Input:
The first line consists of two integers $$N$$ and $$M$$ denoting the number of students and the number of relationships respectively. The next $$M$$ lines consists of two integers $$u$$ and $$v$$ denoting that student $$u$$ and student $$v$$ are friends. $$u$$ and $$v$$ can never be equal and relationships are not repeated.

Output:
Print the answer modulo $$10^9+7$$ in a single line.

Constraints:
$$1 \leq N \leq 10^5$$
$$1 \leq M \leq 10^5$$
$$1 \leq u, v \leq N$$

SAMPLE INPUT
5 4
1 2
2 3
1 3
4 5
SAMPLE OUTPUT
6
Explanation

According to the sample test case,
$$1$$, $$2$$ and $$3$$ must be in the same group.
$$4$$ and $$5$$ must be in the same group.
So, number of ways to choose leaders from these groups is $$3 * 2 = 6$$.

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, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

Code Monk (Disjoint Set Union (Union Find))

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications