Background

As the election approaches, the president will give speeches in city $1$ and city $2$. He travels by car on a campaign tour, starting from $1$, passing through city $2$ on the way, and finally must return to city $1$. The Secret Service monitors all cities the president passes through. To minimize the cost, the number of monitored cities must be as small as possible. Find the minimum number of cities that need to be monitored.

Problem 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