Cow Traffic

The booming cow population on the farm has caused serious congestion on the trails leading to the barn. Farmer John has decided to run a study to find the bottlenecks and relieve the 'traffic jams' at milking time.

The pasture is a network of $M$ one-way trails ($1 \le M \le 50{,}000$), each connecting two different intersections chosen from the $N$ intersections ($1 \le N \le 5{,}000$) numbered $1$ through $N$; the barn is at intersection $N$. Every trail runs from a lower-numbered intersection to a higher-numbered one, so there are no cycles and, as they say on the farm, all trails lead to the barn. A pair of intersections may be joined by more than one trail.

During the milking-time rush hour, the cows leave their grazing locations and head for the barn. The grazing locations are exactly the intersections that have no trails leading into them. Each cow follows a 'path', a sequence of trails from a grazing location to the barn.

Help Farmer John find the busiest trail by computing the largest number of paths that pass through any single trail. The answer is guaranteed to fit in a signed 32-bit integer.

• Line 1: Two space-separated integers $N$ and $M$.
• Lines 2 through $M+1$: Two integers describing one one-way trail. The trail runs from the lower-numbered intersection to the higher-numbered one.

• Line 1: The maximum number of paths that pass through any single trail.