Bicycle Race

Time limit1sMemory limit128 MB

Summary

Given a graph where every edge belongs to at most one cycle, find the longest walk ending at city 1 using each edge at most once.

Level: Hard8 of 10
Topics: Tree, Dynamic programming, Graph
Solved: No attempts yet

Problem

There is a connected graph with N cities and M bidirectional roads. The cities are numbered from 1 to N.

We use the following terms.

A path is a sequence of roads where the destination city of each road is the starting city of the next road.
A simple path is a path that does not visit the same city more than once.
A ring is a simple path whose starting city and ending city are the same.

There is at least one path between every pair of cities, and each road belongs to at most one ring.

You want to build a race route that ends at city 1 while using each road at most once. The starting city may be any city, and the same city may be visited multiple times. Find the maximum possible length of such a route. The length of a route is the number of roads used.

Input

The first line contains the number of cities N and the number of roads M. (2 ≤ N ≤ 10,000, 1 ≤ M ≤ 2N - 2)

Each of the next M lines contains two different integers A and B. (1 ≤ A, B ≤ N) This means there is a bidirectional road between city A and city B. No two roads connect the same pair of cities.

Output

Print the length of the longest race route that ends at city 1.

Examples3

Example 1
Input
```
4 3
1 2
1 3
2 4
```
Expected output
```
2
```
Example 2
Input
```
6 6
1 2
1 3
2 4
3 4
3 5
5 6
```
Expected output
```
5
```
Example 3
Input
```
5 6
1 2
2 3
3 4
4 5
5 3
3 1
```
Expected output
```
6
```