THE PUBLIC LIBRARY

The road map of a remote island of the country is given. On the island, there are N villages (numbered from ~1~ to ~N~) connected by M roads, each of which is bidirectional and connects two villages. Assume that it is possible to travel from any village on the island to any other via the roads of the road network.

Until today, there is no public library on the island. Ideally, each village should have its own library. However, the public funds are sufficient for only one public library, which must necessarily be placed in one of the villages on the island.

We call the "distance" of a village from the library the minimum number of roads that must be traversed to reach it from the village (i.e., the number of edges in the shortest path). For example, if the library is placed in village ~1~, then village ~1~ is at a distance of ~0~ from the library. If village ~2~ is adjacent to ~1~ (i.e., directly connected to it by a road), then village ~2~ is at a distance of ~1~ from the library. If village ~3~ is adjacent to ~2~ but not adjacent to ~1~ (i.e., directly connected to village ~2~ but not to village ~1~), then village ~3~ is at a distance of ~2~ from the library, and so on.

We want to place the library in such a way that the distance from the farthest village to it is minimized.

Problem

Develop a program in one of the IOI languages (PASCAL, C, C++, Java) that reads the road map of the island and prints the distance of the farthest village from the library, assuming it is placed in the optimal position.

Input Files:

The input files named publib.in are text files with the following structure: In the first line, there are two positive integers separated by a single space: the number of villages N and the number of roads M connecting them. Each of the next M lines will contain two positive integers ~U_i~ and ~V_i~, separated by a single space: the numbers of the villages corresponding to the two ends of a road.

Output Files:

The output files named publib.out are text files with the following structure. They must contain exactly one line that includes exactly one integer: the distance of the farthest village from the library, assuming it is placed in the optimal position.

Constraints:

• 1 ~\le N \le~ 2.000, 1 ~\le M \le~ 40.000 and ~N \times M \le~ 10.000.000
• 1 ~\le U_i \le N~, 1 ~\le V_i \le N~, and ~U_i~ ≠ ~V_i~, for each ~i~, where 1 ~\le i \le M~
• There will not be two roads connecting the same villages.

Example of Input - Output Files :

STDIN (publib.in)

8 9
8 6
4 2
1 5
8 1
3 7
4 6
5 2
7 1
2 8

STDOUT (publib.out)

3

Explanation of the example:

The road map of the example is shown in the diagram on the previous page. If we place the library in village ~1~, then the farthest village from it is ~4~, and its distance is ~3~ (e.g., following the roads ~4~-~6~, ~6~-~8~, ~8~-~1~). Similarly, if we place the library in either village ~5~ or ~8~: in both cases, the farthest village is ~3~, and its distance is ~3~. There is no way to place the library so that the farthest village has a distance less than ~3~.

Notes:

Formatting: In both the input and the output, each line terminates with a newline character.
Maximum execution time: 1sec.
Maximum available memory: 64MB.
Headers in the source code: At the beginning of your source code, you should use the following headers.

(* USER: username
LANG: PASCAL
TASK: publib *)

for PASCAL coders

/* USER: username
LANG: C
TASK: publib */

for C coders

/* USER: username
LANG: C++
TASK: publib */

for C++ coders

/* USER: username
LANG: Java
TASK: publib */

for Java coders

# USER: username
# LANG: Python
# TASK: publib

for Python coders