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
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Jogging Cats

Jogging Cats

Problem
Submissions
Leaderboard
Discussions
Editorial

It's almost summertime, so Big Cat and Little Cat are getting in shape. They decide the core of their fitness plan is to start jogging every day.

Their city consists of intersections connected by bidirectional roads. The cats decide that their jogging route should be cyclic (i.e., starting and ending at the same intersection) and consist of different roads.

The cats also love exploring new places, so each day they want to choose a new route to jog on that is not equal to any of their previous routes. Two routes are considered to be equal if their sets of component roads are equal.

Given a map of the city, can you help our heroic cats determine the maximum number of days they can go jogging so that every route traveled is different?

Input Format

The first line contains a pair of space-separated integers, (the number of intersections) and (the number of roads), respectively.

Each line of the subsequent lines contains a pair of space-separated integers, and , defining a bidirectional road connecting intersections and .

Constraints

  • Each bidirectional road connects distinct intersections (i.e., no road connects an intersection to itself).
  • Each pair of intersections is directly connected by no more than road.

Output Format

Print the maximum number of days for which the cats can go jogging without repeating a route.

Sample Input

4 6
1 2
2 3
3 4
4 1
1 3
2 4

Sample Output

3

Explanation

There are different routes:

Recall that each route is a set of intersections forming a cycle, so each unique route is the same regardless of which city on the route the cats start out at. Thus, we print (the number of routes) as our answer.

Author

zxqfd555

Difficulty

Advanced

Max Score

80

Submitted By

712

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

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