Courier Convoys

Difficulty: 2200 4000 ms 128 MB

graphs flow

How many pairwise EDGE-disjoint directed paths run from node 1 to node N?

Input: the first line has N and M; each of the next M lines has a directed edge u v.

Output: the maximum number of edge-disjoint 1 → N paths.

Constraints:

• 2 ≤ N ≤ 500
• 1 ≤ M ≤ 2000

Sample Tests

4 5
1 2
2 4
1 3
3 4
2 3

2

2 2
1 2
1 2

2

Read the Editorial