Longest Simple Path

You are given an undirected graph with n checkpoints (vertices) and m direct routes (edges). Your task is to determine the length of the longest simple path in the graph. A simple path is defined as a path that does not visit the same checkpoint more than once. If a path consists of checkpoints \(v_1, v_2, \ldots, v_k\), its length is \(k-1\), which is the number of edges in the path.

Note that the graph may be disconnected, and you are allowed to start the path at any checkpoint. The input guarantees that the number of checkpoints and routes will be small enough to allow an exponential solution (using DFS) without timing out.

inputFormat

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

 n m
 u1 v1
 u2 v2
 ...
 um vm

Where n is the number of checkpoints, m is the number of direct routes, and each of the next m lines contains two integers u and v indicating a direct route between checkpoints u and v.

outputFormat

Print a single integer to stdout representing the length (number of edges) of the longest simple path in the graph.

6 7
1 2
2 3
3 4
1 3
1 4
4 5
5 6

5