Minimize Graph Diameter After Adding a Zero‐Weight Edge

Given a simple connected undirected graph with n vertices and m edges, where each edge has a weight of 1, you are allowed to add one extra edge with weight 0. Your task is to choose an optimal pair of vertices (u, v) such that after adding the edge between them, the diameter of the new graph is minimized.

The diameter of a graph is defined as

[ D = \max_{1 \leq i, j \leq n} {\operatorname{dist}(i,j)}, ]

where \(\operatorname{dist}(i,j)\) is the shortest distance between vertices \(i\) and \(j\) in the modified graph. When adding the extra edge between vertices a and b (with weight 0), the new distance between any two vertices \(u\) and \(v\) would be:

[ \min\Big( d(u,v),; d(u,a)+d(b,v),; d(u,b)+d(a,v) \Big), ]

where \(d(u,v)\) denotes the shortest distance in the original graph. You only need to output the minimum possible diameter after adding the extra edge optimally.

inputFormat

The first line contains two integers n and m (the number of vertices and edges, respectively).

Each of the following m lines contains two integers u and v, representing an edge between vertex u and vertex v (1-indexed). It is guaranteed that the graph is simple and connected.

outputFormat

Output a single integer --- the minimum possible diameter of the graph after adding one extra edge of weight 0 optimally.

sample

3 2
1 2
2 3

1