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 path is a sequence of roads such that each road starts from the ending city of the previous road.

• A simple path is a path that does not visit any city more than once.

• A cycle is a simple path whose starting city and ending city are the same.

For any pair of cities, it is guaranteed that there is at least one path between them, and each road in the entire transportation system belongs to at most one cycle.

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

• The path may start from any city, but it must end at city $1$.

• The path may visit the same city multiple times, but it must not pass through the same road more than once.

Output the length of the longest path.

Input Format

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

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

It is guaranteed that there are no multiple roads directly connecting the same pair of cities.

Output Format

Output the length of the longest path.

4 3
1 2
1 3
2 4

2

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

5

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

6

Hint

Constraints

For $100\%$ of the testdata, 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

Translated by ChatGPT 5