P6134 [JSOI2015] Minimum Representation

Do you still remember the problem about strongly connected components studied by JYY last year? In last year’s problem, JYY studied the “adding edges” problem on directed graphs. Having a strong interest in graph theory, JYY this year started thinking about the “deleting edges” problem.

Given a directed graph with $N$ vertices (each vertex is numbered from $1$ to $N$) and $M$ edges, JYY found that if some edges are deleted from the graph, the connectivity of the original graph may change; meanwhile, there are also some edges such that deleting them will not change the connectivity of the graph. JYY wants to know: if we want to keep the connectivity between any two vertices in the original graph unchanged, what is the maximum number of edges we can delete? To simplify the workload, this time JYY guarantees that the given directed graph is a directed acyclic graph (DAG) (JYY: after last year’s problem, everyone knows that problems on arbitrary directed graphs can eventually be transformed into problems on DAGs, so this year JYY simply made it easier).

The first line contains two positive integers $N$ and $M$. The next $M$ lines each contain two positive integers $x_i$ and $y_i$ between $1$ and $N$, indicating that there is a directed edge from $x_i$ to $y_i$ in the graph. The input guarantees that between any two vertices, there is at most one edge.

Output one line containing one integer, which is the maximum number of edges that JYY can delete.

### Sample Explanation One valid plan is to delete $1\rightarrow 5$ and $1\rightarrow 3$. It is easy to prove that there is no better answer than $2$. ### Constraints For $100\%$ of the data, $1 \leq N\leq 3\times 10^4$, $0 \leq M\leq 10^5$. Translated by ChatGPT 5