Evacuation

Because of a growing terrorist threat, the Agency for Defending Byteland (ADB) has decided to prepare a plan of action for the case of an attack. The agency's key concern is making sure that the king of Byteland can be evacuated quickly whenever a bombing takes place.

The royal palace stands next to one of the junctions in the capital of Byteland, and a shelter stands next to another junction; in case of danger the king must be moved there at once. The ADB has an exact road map of the capital, made up of junctions joined by one-way streets.

An evacuation route counts as quick if it uses at most three streets. When a bombing hits a street, that street becomes impassable for the royal convoy. The ADB wants to know the minimum number of streets that must be bombed so that the king is left with no quick evacuation route at all.

The first line contains two integers $n$ and $m$ ($2 \le n \le 1000$, $0 \le m \le n(n-1)$): the number of junctions and the number of streets in the capital. Junctions are numbered from $1$ to $n$; the royal palace is next to junction $1$ and the shelter is next to junction $n$.

Each of the next $m$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$), describing a one-way street that runs from junction $a_i$ to junction $b_i$. For every ordered pair of junctions there is at most one street going from the first one to the second one.

Print a single integer: the minimum number of streets that must be bombed so that the king has no evacuation route using at most three streets.

In the picture above it is enough to bomb the streets $1 \to 3$ and $3 \to 5$ (shown crossed out) so that no quick evacuation route remains.