Longest Path in a Star-Shaped Grid

You are given an undirected graph representing a star-shaped grid. The grid consists of N nodes and M edges. Your task is to determine the length of the longest simple path (i.e. a path which does not visit any vertex more than once) in the grid. In the case of a disconnected graph (i.e. a forest), you should consider each connected component and output the maximum length among them.

Note: The longest path in a connected component is equivalent to the diameter of that component, which can be computed using two breadth-first searches (BFS). First, choose an arbitrary node and find the farthest node from it. Then, from that farthest node, perform another BFS to find the maximum distance; this distance is the diameter of that component.

It is guaranteed that nodes are numbered from 1 to N.

inputFormat

The input is given from stdin and has the following format:

N
M
u1 v1
u2 v2
...
uM vM

Where:

• N is the number of nodes.
• M is the number of edges.
• Each of the next M lines contains two space-separated integers u and v representing an undirected edge between nodes u and v.

outputFormat

Output a single integer to stdout representing the length of the longest simple path in the grid.

5
4
1 2
2 3
3 4
4 5

4