Shortest Cycle in an Undirected Graph

This problem requires you to determine the length of the shortest cycle in a given undirected graph. The graph is defined by N vertices and M edges. A cycle is a sequence of vertices starting and ending at the same vertex with each consecutive pair of vertices connected by an edge.

The length of a cycle is the number of edges it uses. If there is no cycle present, your program should output -1. Note that the vertices are numbered from 0 to N - 1.

Your task is to read the graph from standard input and compute the length of its shortest cycle using an efficient algorithm, such as breadth-first search (BFS).

inputFormat

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

N M
u1 v1
u2 v2
...
uM vM

Here, N is the number of vertices, M is the number of edges, and each of the following M lines contains two integers u and v that represent an undirected edge between vertices u and v.

outputFormat

Output a single integer to standard output (stdout), which is the length of the shortest cycle in the graph. If no cycle exists, output -1.

4 4
0 1
1 2
2 0
2 3

3