Ranking the Cows

Farmer John has $N$ cows ($1 \le N \le 1000$), each producing milk at a different positive rate. FJ would like to order his cows from the fastest milk producer to the slowest.

He has already compared the milk output rates of $M$ pairs of cows ($1 \le M \le 10000$). He now wants to prepare a list of $C$ additional pairs of cows such that, once he also compares those $C$ pairs, he will definitely be able to deduce the complete ordering of all $N$ cows. Determine the minimum value of $C$ for which such a list is possible.

• Line 1: Two space-separated integers $N$ and $M$.
• Lines 2..M+1: Two space-separated integers $X$ and $Y$ ($1 \le X, Y \le N$), describing a known comparison in which cow $X$ was ranked higher (produces milk more quickly) than cow $Y$.

• Line 1: A single integer, the minimum value of $C$.

Suppose FJ is comparing 5 cows and has already determined that cow 2 > cow 1, cow 1 > cow 5, cow 2 > cow 3, cow 1 > cow 4, and cow 3 > cow 4 (where '>' means "produces milk more quickly").

From these 5 results, FJ knows that cow 2 has the highest rank, since cow 2 > cow 1 > cow 5 and cow 2 > cow 3 > cow 4. However, he still needs to compare cow 1 with cow 3 to decide the second-highest cow, one more comparison to order cow 4 and cow 5, and (if cow 1 outranks cow 3) a comparison of cow 5 with cow 3. He therefore must ask three questions to be certain of the full ranking: "Is cow 1 > cow 3? Is cow 4 > cow 5? Is cow 5 > cow 3?"