The Shortest Loop

Difficulty: 2000 6000 ms 128 MB

bfs graphs

Print the length (number of edges) of the shortest cycle (girth) in an undirected simple graph, or −1 if it is acyclic.

Input: the first line has N and M; each of the next M lines has an edge u v.

Output: the girth, or −1.

Constraints:

• 1 ≤ N ≤ 10³
• 0 ≤ M ≤ 2×10³

Sample Tests

4 4
1 2
2 3
3 4
4 1

4

3 2
1 2
2 3

-1

Read the Editorial