Shortest Cycle in an Undirected Graph

You are given an undirected graph with \( n \) nodes and \( m \) edges. The nodes are numbered from 1 to \( n \). Your task is to find the length of the shortest cycle in the graph.

A cycle is defined as a sequence of edges where the first and last vertex are the same and all edges and vertices (except the starting and ending vertex) are distinct. If no cycle exists, you should output \( -1 \).

Constraints:

• \( 1 \leq n \leq 500 \)
• \( 0 \leq m \leq 10000 \)
• Each edge connects two different nodes \( u \) and \( v \) where \( 1 \leq u, v \leq n \) and \( u \neq v \).

Input/Output: The input is read from stdin and the output is written to stdout.

inputFormat

The first line contains two integers \( n \) and \( m \) separated by a space, where \( n \) is the number of nodes and \( m \) is the number of edges.

The next \( m \) lines each contain two integers \( u \) and \( v \), representing an undirected edge between nodes \( u \) and \( v \).

Example:

4 5
1 2
2 3
3 1
2 4
4 3

outputFormat

Output a single integer which is the length of the shortest cycle in the graph. If there is no cycle, output \( -1 \).

## sample

4 5
1 2
2 3
3 1
2 4
4 3

3