Shortest Simple Cycle in an Undirected Graph

You are given an undirected graph for each test case. Your task is to determine the length of the shortest simple cycle in the graph.

A simple cycle is a cycle in which no vertices (except the starting and ending vertex) are repeated. If no cycle exists in the graph, then the answer should be -1.

The input consists of multiple test cases. For each test case, the first line contains two integers \(N\) and \(M\), where \(N\) is the number of vertices and \(M\) is the number of edges. The following \(M\) lines contain two integers \(u\) and \(v\) each, representing an undirected edge between vertices \(u\) and \(v\).

Your solution must read input from standard input (stdin) and output the results on standard output (stdout), printing one result per test case.

inputFormat

The input starts with an integer \(T\) representing the number of test cases. Each test case is described as follows:

• The first line contains two integers \(N\) and \(M\): the number of vertices and edges, respectively.
• The next \(M\) lines each contain two integers \(u\) and \(v\), indicating an undirected edge between vertices \(u\) and \(v\).

outputFormat

For each test case, output a single line with one integer: the length of the shortest simple cycle in the graph, or -1 if no such cycle exists.

## sample

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

3
-1

</p>