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.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Jogging Cats

Jogging Cats

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.