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.

riseoj 작성

출처 COCI 2007/2008 Contest 1