Shortest Cycle in an Undirected Graph

You are given an undirected graph with $N$ vertices and $M$ edges. Your task is to find the length of the shortest cycle in the graph. A cycle is a path that starts and ends at the same vertex and contains at least three distinct vertices. If the graph does not contain any cycle, output -1.

A suggested approach is to use breadth-first search (BFS) starting from each vertex, while keeping track of the distance from the start vertex. When a previously visited vertex (that is not the immediate parent) is encountered, a cycle is detected. The length of such a cycle is computed as:

$length = dist[u] + dist[v] + 1$

The answer is the minimum cycle length over all starting vertices, or -1 if no cycle exists.

inputFormat

The first line contains two integers $N$ and $M$, representing the number of vertices and edges in the graph respectively. The following M lines each contain two integers $u$ and $v$, indicating that there is an undirected edge between vertices $u$ and $v$.

outputFormat

Output a single integer representing the length of the shortest cycle in the graph. If no cycle exists, output -1.

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

4