Longest Path in an Undirected Graph

You are given an undirected graph with N nodes and M edges. The nodes are numbered from 1 to N. Your task is to determine the length of the longest simple path in the graph — essentially, the graph's diameter within the connected component that includes node 1.

This problem can be solved with a two-step breadth-first search (BFS):

• First, perform a BFS starting from node 1 to find the farthest node from node 1.
• Second, perform another BFS from this farthest node to determine the maximum distance from it.

The distance obtained in the second BFS is the length of the longest path. Note that if the graph is disconnected, only the connected component containing node 1 is considered.

Mathematical representation:

Let \(G=(V,E)\) be an undirected graph. Define the distance between two nodes \(u\) and \(v\) as the minimum number of edges in a path connecting them, denoted \(d(u,v)\). The task is to compute:

\[ \max_{u,v \in C(1)} d(u,v), \]

where \(C(1)\) is the connected component containing node 1.

inputFormat

The first line contains two integers N and M — the number of nodes and edges, respectively.

Then M lines follow, each containing two integers u and v indicating that there is an undirected edge between nodes u and v.

outputFormat

Output a single integer — the length of the longest path (i.e. the diameter of the connected component that includes node 1).

## sample

1 0

0

</p>