Description

There are $N$ cities and $M$ directed edges, satisfying $2 \le N \le 100, 2 \le M \le 200$.

We need to find, among all routes that start from city $1$, pass through city $2$ on the way, and finally return to city $1$, the minimum number of cities that need to be visited. The testdata guarantees that a solution exists.

Input Format

The first line contains two integers $N, M$. $N$ is the number of cities, and $M$ is the number of directed edges.

The next $M$ lines each contain two integers $A, B$, indicating a directed edge from $A$ to $B$.

Output Format

Output the minimum number of cities that need to be monitored.

6 7
1 3
3 4
4 5
5 1
4 2
2 6
6 3

6

Hint

For $100\%$ of the testdata, $2 \le N \le 100, 2 \le M \le 200$ holds.

The testdata for this problem is strengthened by Imagine.

Translated by ChatGPT 5