Minimum Cities Cycle Through Node 2

Given a directed graph with \(N\) cities and \(M\) edges (where \(0 \leq N, M \leq 200\)), you are to find a cycle starting at city 1 that must pass through city 2 and then return to city 1, using the minimum number of visited cities. In other words, let the path from 1 to 2 consist of \(d_{1}\) cities and the path from 2 back to 1 consist of \(d_{2}\) cities. The answer is defined as \(d_{1} + d_{2} - 1\) (note that city 2 is counted in both paths). If no such route exists, output -1.

The graph is given as a list of directed edges. Each edge is represented by two integers \(u\) and \(v\), indicating a directed edge from \(u\) to \(v\>.

inputFormat

The first line contains two integers \(N\) and \(M\) separated by a space.

Each of the following \(M\) lines contains two integers \(u\) and \(v\) indicating there is a directed edge from city \(u\) to city \(v\>.

outputFormat

Output a single integer representing the minimum number of cities visited along a route starting from city 1, passing through city 2, and finally returning to city 1. If no such route exists, output -1.

sample

3 3
1 2
2 3
3 1

4