Minimum Helicopter Flights for Slope Cleaning

A ski resort is located on several mountains in the northwest of FJ province. When viewed from the air, the resort can be represented as a directed acyclic graph (DAG), where each arc corresponds to a slope and the direction of the arc indicates the downhill direction.

Your team is responsible for clearing the slopes every week. You have a helicopter that in each flight can carry one person from the headquarters to any location in the resort, after which the helicopter returns to the headquarters. The person, starting at the drop‐off point, will slide downhill along a simple path, clearing every slope they traverse.

Since each helicopter flight has a fixed cost, you want to minimize the number of flights needed to clean every slope (i.e. cover every arc in the graph with at least one downward path). Determine the minimum number of flights required.

Formalization: The ski resort is given as a DAG with n nodes and m directed edges. A flight corresponds to a path in the DAG. You must select a set of paths such that every edge is contained in at least one path. Output the minimum number of paths needed.

Hint: Note that if you can chain two edges (i.e. if the tail of one edge is the head of another), then they can be cleaned in a single flight. The problem reduces to partitioning the edge set into a minimum number of directed paths. In fact, if x is the maximum number of pairs of consecutive edges you can combine (without reusing an edge as the second in more than one pair), then the answer is m - x. You can solve this by constructing a bipartite graph where both parts represent the set of edges and an edge from e (in the left part) to f (in the right part) exists if the ending vertex of e is equal to the starting vertex of f, and then computing a maximum matching.

inputFormat

The first line contains two integers n and m (n is the number of nodes, m is the number of slopes). Each of the following m lines contains two integers u and v, indicating a directed edge (slope) from node u to node v in the graph.

outputFormat

Output a single integer representing the minimum number of helicopter flights required to clear all slopes.

sample

3 2
1 2
2 3

1