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

Teacher's Dilemma

Disjoint data structures, Disjoint set, Disjoint set, approved


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.

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.

Print the answer modulo \(10^9+7\) in a single line.

\(1 \leq N \leq 10^5\)
\(1 \leq M \leq 10^5\)
\(1 \leq u, v \leq N\)

5 4
1 2
2 3
1 3
4 5

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

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications