SOLVE
LATER
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\)
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\).
Challenge Name
Code Monk (Disjoint Set Union (Union Find))
Code Monk (Disjoint Set Union (Union Find))