Ikshu and his class
Practice
3.9 (8 votes)
Algorithms
Approved
Data structures
Depth first search
Disjoint set
Medium
Open
Problem
51% Success 3427 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

Ikshu and his class

Ikshu's class is very fond of playing games. Their teacher tied them with many ropes with each other, Such that each student is tied with exactly one rope. It means that if students 2 and 3 are connected and 2 is connected to 4 as well then 2,3 and 4 must be sharing the same rope.

Now, teacher asks them to divide themselves in group. One group for each rope, each group consists of the students tied to that particular rope. Each group exchanges gifts among themselves (each student is having exactly one gift before and after the game).

What is the total number of distinct exchanges possible ? Two exchanges are distinct if there is atleast one student having different gift with him.

NOTE: It is also possible that a student has same gift after exchanging as he had before exchanging. There might be a case where no exchange took place i.e each student is having same gift after exchanging as he was having before exchange.

Input:
First line of input contains two integers N and K, where N is the number of students and K is the number of connections between students. Next K lines contains two integers which are the indices(0 based) of students connected by a rope.

Output:
Print a single integer which is the total number of exchanges possible modulus (10^9 + 7)

Constraints:
1 <= N <= 100000
1 <= K <= 100000

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
55 votes
Tags:
ApprovedData StructuresDisjoint setMediumOpen
Points:30
8 votes
Tags:
Data StructuresDisjoint setMediumString Manipulation
Points:30
8 votes
Tags:
Data StructuresDisjoint Data StructuresDisjoint SetDisjoint setImplementationMedium