Consider the property of a cycle containing vertex \(1\) with the minimum number of edges.

Suppose that one of the cycles containing vertex \(1\) with the minimum number of edges consists of \((k+1)\) edges: vertex \(1\) \(\to\) vertex \(v_1\) \(\to\) \(\dots\) \(\to\) vertex \(v_k\) \(\to\) vertex \(1\). Then, \(v_k\) has the following property:

the distance from vertex \(1\) to vertex \(v_k\) is \(k\).

(Proof) The path vertex \(1\) \(\to\) vertex \(v_1\) \(\to\) \(\dots\) \(\to\) vertex \(v_k\) has a length of \(k\), so the distance from vertex \(1\) to vertex \(v_k\) is at most \(k\). If there is a path of length less than \(k\), then appending the edge vertex \(v_k\) \(\to\) vertex \(1\) forms a cycle of length less than \((k+1)\), contradicting the assumption that the original cycle has the minimum number of edges. Thus it has been proved. (End of proof)

By this fact, it turns out that the distance from vertex \(1\) to each vertex is crucial to find a cycle with the minimum number of edges. This observation leads to the following fact:

Let \(S\) be the set of vertices \(v\) such that:

• vertex \(v\) is reachable from vertex \(1\); and
• there is an edge from vertex \(v\) to vertex \(1\).

Then the answer is as follows:

• if \(S\) is an empty set, there is no conforming cycle;
• if \(S\) is a non-empty set, the answer is \(\min_{v \in S} (\text{distance from vertex }1\text{ to vertex }v)\).

The validity can be proved by the fact that, for the vertex \(v\) that is the previous vertex of vertex \(1\) in a cycle, the distance from vertex \(1\) to vertex \(v\) plus \(1\) is the minimum number of edges in a cycle, as shown above.

By the discussion so far, the Breadth-First Search (BFS) algorithm that finds the shortest distance to each vertex is a valid solution. Specifically, do the process as follows:

• Do BFS to find the distance to each vertex in ascending order of the distances. Inside the BFS, do the following process as well as computing the distances as usual.
  • Let \(c\) be the current vertex. If there is an edge from vertex \(c\) to vertex \(1\), print the distance from vertex \(1\) to vertex \(c\), plus \(1\), as the answer, and terminate the entire procedure.
• If BFS ends before printing anything, then no cycle is detected; print -1.

This algorithm runs in \(\mathrm{O}(N + M)\) time, which is fast enough.

• Sample code (Python)

from collections import deque

N, M = map(int, input().split())
g = [list() for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)

inf = 10**9
d = [inf] * N
Q = deque()

d[0] = 0
Q.append(0)

while len(Q) > 0:
    cur = Q.popleft()
    for dst in g[cur]:
        if dst == 0:
            print(d[cur] + 1)
            exit()
        if d[dst] == inf:
            d[dst] = d[cur] + 1
            Q.append(dst)

print(-1)