Cow Traffic

Time limit1sMemory limit128 MB

Summary

In a DAG where every edge goes from a lower to a higher numbered node, count how many source-to-barn paths cross each edge and output the maximum.

Level: Medium6 of 10
Topics: Graph, Dynamic programming, Topological sort, DFS
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples1

Example 1
Input
```
7 7
1 3
3 4
3 5
4 6
2 3
5 6
6 7
```
Expected output
```
4
```