A dependency graph is a directed acyclic graph on n nodes. An edge u v (u before v) is redundant if the ordering it enforces is already implied by other edges — that is, if there is another directed path from u to v that does not use the edge u v directly. Removing every redundant edge yields the transitive reduction, which for a DAG is unique. Count how many edges remain in the transitive reduction.
Input format
Line 1: two integers n and m — the number of nodes (labeled 0 through n-1) and the number of directed edges.
Each of the next m lines: two integers , a directed edge from to (read as: must come before ).
It is guaranteed the graph is acyclic, with no self-loops and no duplicate edges.
Output format
A single integer: the number of edges in the transitive reduction.
Constraints
- 1 <= n <= 40
- 0 <= m <= 600
- 0 <= u, v <= n-1; the graph is a DAG with no duplicate edges