Shortest Cycle in an Undirected Graph

Given an undirected graph with n vertices and m edges, your task is to determine the length of the shortest cycle in the graph. A cycle is defined as a sequence of at least three distinct vertices, starting and ending at the same vertex, where each consecutive pair of vertices is connected by an edge.

If no cycle exists in the graph, output -1.

The graph may be disconnected and may contain isolated vertices. The input is provided with the number of vertices and edges, followed by m pairs of integers. Each pair represents an undirected edge between two vertices.

This problem can be modeled using breadth-first search (BFS) to detect cycles. A cycle of length L is detected when, during BFS, a previously visited vertex (that is not the direct parent) is encountered, and the length is given by the formula:

\( L = d(u) + d(v) + 1 \)

inputFormat

The first line contains two integers n and m — the number of vertices and edges respectively. Each of the following m lines contains two integers u and v representing an undirected edge between vertices u and v.

outputFormat

Output a single integer: the length of the shortest cycle in the graph, or -1 if no cycle exists.## sample

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

3