Longest Simple Path

You are given a road network represented as an undirected graph with n intersections and m roads. Each road connects two intersections. A simple path is a path that does not visit any vertex more than once. Your task is to determine the length of the longest simple path in this network.

More formally, if a simple path is defined by a sequence of vertices \(v_1, v_2, \ldots, v_k\) such that \(v_i\) and \(v_{i+1}\) are directly connected by a road for \(1 \le i < k\) and \(v_i \neq v_j\) for all \(i \neq j\), then the length of the path is \(k-1\). You need to find the maximum possible length among all simple paths in the network.

Note that the network might be disconnected.

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

n m
u1 v1
u2 v2
... 
um vm

Here, the first line contains two integers \(n\) and \(m\) representing the number of intersections and roads, respectively. Each of the following \(m\) lines contains two integers \(u\) and \(v\) indicating that there is a bidirectional road between intersections \(u\) and \(v\).

outputFormat

Output a single integer to standard output (stdout) which is the length of the longest simple path in the network.

5 4
1 2
2 3
3 4
4 5

4