Description

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).

Input Format

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 Format

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

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

2

Hint

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