Round Trips

Image by
Nejron Photo (Shutterstock), Used under license

Micah lives a peaceful life with his family in one of Canada’s most beautiful provinces. The vast wealth he has accumulated allows him to indulge in an extravagant hobby: collecting vintage automobiles. On Sunday afternoons, Micah and his family enjoy taking long, leisurely drives in these classic cars. Because of the unusual road system in the province, they have made something of a game out of planning their weekly outings.

Micah’s province contains $n$ towns that are connected by a
network of roads. Every road joins some town $x$ to a different
town $y$, and all
roads are *one-way (!)* There is never more than
one road from any town $x$ to any other
town $y$ (although
there may be a road going in the reverse direction), and other
than the fact that roads may meet at their endpoints (towns),
no two roads intersect (this is facilitated by an elaborate
system of overpasses and underpasses).

Each Sunday after lunch, Micah and his family plan and then
embark on what they call a *round trip*. This involves
first going to one of the $n$ towns (via helicopter, of course;
driving there would detract from the graph theoretic purity of
the entire excursion), getting into one of Micah’s fine cars
(also transported there by helicopter), and then driving from
town to town along the various one-way roads in such a way that
they always end up back at the town where they started
(whereupon helicopters transport everyone/everything back
home). There is one family cardinal rule: during one of these
round trips, they can never drive along the same road twice.
Overall, a round trip can be represented as a sequence of
towns

where (a) $T \geq 2$, (b) $x_0 = x_ T$ is the starting town, (c) there is a (one-way) road from $x_ i$ to $x_{i+1}$ for $0 \leq i < T$, and (d) no road is repeated. Note that $x_0, x_1, \ldots , x_{T-1}$ are not necessarily all distinct.

In their endless quest for adventure, Micah and his family
have decided that they never want to take the same round trip
twice, so Micah has designed a simple algorithm to count
exactly how many round trips are possible. It saddens them,
though, when this algorithm reveals that this number is in fact
*finite*, which means that one day they will have used
up all the possible round trips. However, there is hope! From
time to time, the province constructs a new road, which is very
exciting because a new road may mean new round trips.
Unfortunately, Micah’s evil twin, Hacim (separated at birth),
has recently been appointed Director of the Inter-County Paving
Commission (ICPC), and he is determined to use his new power to
minimize all this vexing family-oriented fun. Hacim cannot
prevent the construction of new roads altogether, of course
(that would eventually get him fired), but he *can*
influence which new roads get constructed. For Hacim, “fun”
means approving the construction of a new road that does not
create any new round trips for Micah and his family. Hacim
wonders how long he can continue doing this, i.e., how many new
roads can be constructed without creating any new round trips.
Since he is not as good as Micah at designing counting
algorithms, he needs your help to figure this out.

Note that a new road, like an existing road, can meet other roads at its endpoints, but otherwise it cannot intersect any other road. Also, the construction of new roads is, of course, cumulative (roads never get removed).

The first line of input contains two space-separated integers, $n$ and $m$ ($1 \leq n \leq 100\, 000$, $0 \leq m \leq 200\, 000$), where $n$ is the number of towns (indexed $0, 1, \ldots , n-1$) and $m$ is the number of one-way roads. This is followed by $m$ lines, each containing two space-separated integers, $x$ and $y$ ($0 \leq x,y \leq (n-1)$, $x \neq y$), indicating that there is a one-way road from town $x$ to town $y$. No road will be specified more than once.

Output a single integer, the maximum number of one-way roads that can be constructed without creating any new round trips.

Sample Input 1 | Sample Output 1 |
---|---|

2 1 0 1 |
0 |

Sample Input 2 | Sample Output 2 |
---|---|

5 7 3 2 4 0 3 1 0 3 4 2 1 0 3 4 |
2 |