Shortest Cycle in an Undirected Graph

You are given an undirected graph with \(n\) nodes (indexed from 0) and \(m\) edges. Your task is to determine the length of the shortest cycle within the graph. A cycle is defined as a path that starts and ends at the same node and contains at least one edge. If no cycle exists, output -1.

For instance, the distance between two nodes during a breadth-first search can be understood as the number of edges traversed. Hence, if a cycle is found by encountering a previously visited node (that is not the immediate parent), the length of the cycle is computed as \(distance[u] + distance[v] + 1\), where \(u\) and \(v\) are the current node and its neighbor respectively.

inputFormat

The input is read from standard input (stdin). The first line contains two integers \(n\) and \(m\), where \(n\) is the number of nodes and \(m\) is the number of edges. Each of the following \(m\) lines contains two integers \(u\) and \(v\) indicating an undirected edge between nodes \(u\) and \(v\). Note that self-loops (edges from a node to itself) may occur.

outputFormat

Output a single integer representing the length of the shortest cycle in the graph, or -1 if there is no cycle.

5 6
0 1
1 2
2 3
3 4
4 1
4 2

3