Problem Description

A bicycle race will be held in a country. The national transportation network consists of $n$ cities, numbered from $1$ to $n$, connected by $m$ bidirectional roads. We define the following terms:

• A route is a sequence of roads such that each road starts from the ending city of the previous road.

• A simple route is a route that does not pass through any city more than once.

• A loop is a simple route that starts and ends at the same city.

For any two cities, there is guaranteed to be at least one route between them, and each road in the entire transportation system is part of at most one loop.

Your task is to find the longest route that satisfies the following two constraints:

• The route can start from any city but must end at city $1$.

• The route can visit the same city multiple times but cannot pass through the same road more than once.

Output the length of the longest route.

Input Format

The first line of input contains two integers $n$ and $m$, representing the number of cities and the number of roads, respectively.

The next $m$ lines each contain two integers $a$ and $b$, describing a bidirectional road connecting cities $a$ and $b$.

It is guaranteed that no two cities are directly connected by multiple roads.

Output Format

Output the length of the longest route.

Sample Input and Output

Sample Input #1

4 3
1 2
1 3
2 4

Sample Output #1

2

Sample Input #2

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

Sample Output #2

5

Sample Input #3

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

Sample Output #3

6

Notes

Data Size and Constraints

For $100\%$ of the data, it is guaranteed that $2 \le n \le 10^4$, $1 \le m \le 2n-2$, and $1 \le a, b \le n$.

Notes

Translated from COCI2007-2008 CONTEST #1 T6 STAZA

见题面 Input 部分

见题面 Output 部分