A bicycle race is being organized in a country. The transport network of the country consists of $N$ cities numbered $1$ through $N$, with $M$ bidirectional roads connecting them. We will use the following terms:

  • A path is a sequence of roads in which each road starts in the city the preceding road ended in.

  • A simple path is a path which never visits a city more than once.

  • A ring is a simple path ending in the same city it started in.

The network is such that there is at least one path between every pair of cities. Additionally, every road in the network is part of at most one ring.

Your task is to find the longest path for the race satisfying two constraints:

  • The path may begin in any city, but must end in city $1$.

  • The path may visit a city more than once, but it must not contain any road more than once.


The first line of input contains two integers $N$ and $M$ ($2 \le N \le 10\, 000$, $1 \le M \le 2N-2$) – the numbers of cities and roads in the network.

Each of the following $M$ lines contains two different integers $A$ and $B$ ($1 \le A, B \le N$). These numbers indicate that there is a bidirectional road between cities $A$ and $B$. No two cities will be directly connected by more than one road.


Output the length of the longest race path on a single line.

Sample Input 1 Sample Output 1
4 3
1 2
1 3
2 4
Sample Input 2 Sample Output 2
6 6
1 2
1 3
2 4
3 4
3 5
5 6
Sample Input 3 Sample Output 3
5 6
1 2
2 3
3 4
4 5
5 3
3 1
CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 6.7hard
Statistics Show
License For educational use only

Please log in to submit a solution to this problem

Log in