Maximum Removable Edges in a DAG While Preserving Connectivity

Given a directed acyclic graph (DAG) with $$N$$ nodes (numbered from $$1$$ to $$N$$) and $$M$$ edges, determine the maximum number of edges that can be removed such that for any two nodes, their connectivity remains unchanged. In other words, if there exists a path from node $$u$$ to node $$v$$ in the original graph, there must still exist a path from $$u$$ to $$v$$ after the removal of some edges.

It can be shown that the minimal set of edges that preserves the reachability relation of a DAG is its transitive reduction. Hence, the answer equals $$M - (\text{number of edges in the transitive reduction})$$.

Note: The input graph is guaranteed to be a DAG.

inputFormat

The first line contains two integers $$N$$ and $$M$$, representing the number of nodes and edges respectively. Each of the following $$M$$ lines contains two integers $$u$$ and $$v$$, denoting a directed edge from node $$u$$ to node $$v$$.

Constraints: The graph is a Directed Acyclic Graph (DAG).

outputFormat

Output a single integer representing the maximum number of edges that can be removed while preserving the original connectivity of the graph.

sample

3 3
1 2
2 3
1 3

1