Smallest Follow Loop

In a social network consisting of n users, the following relationship between users is represented as a directed edge. Given n (the number of users) and a list of m following relationships, your task is to determine the length of the smallest follow loop (cycle) in the network.

A follow loop is a sequence of distinct users \(v_1, v_2, \ldots, v_k\) such that there is a direct following relationship from \(v_i\) to \(v_{i+1}\) for \(1 \le i < k\) and from \(v_k\) back to \(v_1\). In other words, in the directed graph \(G(V,E)\), find the minimum \(k\) such that there exists a sequence where \(v_1=v_k\) and \((v_i,v_{i+1})\in E\) for all \(1 \leq i < k\).

If no follow loop exists, output -1.

inputFormat

The first line contains two integers n and m where n is the number of users and m is the number of following relationships. The next m lines each contain two integers ai and bi, indicating that user ai follows user bi.

outputFormat

Output a single integer representing the length of the smallest follow loop. If no loop exists, output -1.

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

3