We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Road Maintenance

Road Maintenance

Problem
Submissions
Leaderboard
Discussions
Editorial

Byteland has cities (numbered from to ) and bidirectional roads. A path is comprised of or more connected roads. It is guaranteed that there is a path from any city to any other city.

Steven is a road maintenance worker in Byteland. He is required to maintain exactly paths on any given workday. He cannot work on the same road twice in one day (so no paths can contain the same roads). Steven can start his workday in any city and, once he has finished maintaining a path, teleport to his next starting city.

Given , help Steven determine how many different possible path sets will allow him to perform his maintenance duties. Then print the answer modulo .

Input Format

The first line contains space-separated integers, (the number of cities) and (the number of roads to maintain).
Each line of the subsequent lines contains space-separated integers, , describing a bidirectional road between cities and .

Constraints

Output Format

Find the number of different path sets that will allow Steven to complete orders, and print the answer .

Sample Input

4 2
1 2
2 3
2 4

Sample Output

6

Explanation

For the following Byteland map: Steven can maintain roads using any of the following routes:

  1. and
  2. and
  3. and
  4. and
  5. and
  6. and

Thus, we print the result of on a new line, which is .

Author

nikasvanidze

Difficulty

Hard

Max Score

100

Submitted By

1077

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy