Description

The figure shows a schematic food web of an ecosystem. You are given $n$ species and $m$ energy-flow relations; compute the number of food chains. Species are labeled from $1$ to $n$. The $m$ energy-flow relations are given as pairs $a_1, b_1, a_2, b_2, a_3, b_3, \ldots, a_{m-1}, b_{m-1}, a_m, b_m$, where $a_i$ and $b_i$ mean that energy flows from species $a_i$ to species $b_i$. Note that a single isolated species does not count as a food chain.

Input Format

The first line contains two integers $n, m$. The next $m$ lines each contain two integers $a_i$ and $b_i$ describing the $m$ energy-flow relations.

Output Format

Output a single integer: the number of food chains in the food web.

10 16
1 2
1 4
1 10
2 3
2 5
4 3
4 5
4 8
6 5
7 6
7 9
8 5
9 8
10 6
10 7
10 9

9

Hint

The testdata guarantee that the input conforms to biological properties, and there are no duplicate energy-flow relations. The answer is guaranteed not to overflow a 32-bit signed int.

Constraints: for $100\%$ of the testdata, $1 \leq n \leq 100000$, $0 \leq m \leq 200000$.

Translated by ChatGPT 5