Minimum Additional Comparisons for Complete Cow Ordering

Farmer John has N cows (where \(1 \le N \le 10^3\)) and he wants to order them by their milk production capabilities. He already knows \(M\) pairwise comparisons (\(1 \le M \le 10^4\)). Each comparison is provided in the form X Y, meaning that cow \(X\) produces more milk than cow \(Y\). However, the given information might not be enough to establish a complete ordering among all the cows.

Using the transitivity of the comparisons, some pairs of cows may have an inferred ordering. In order to obtain a complete ordering, Farmer John must have information for every distinct pair of cows \((i, j)\) where \(i \neq j\). A complete ordering requires that the total number of comparisons (direct or inferred) equals \(\frac{N(N-1)}{2}\).

Your task is to determine the minimum number of new comparisons that are still needed to guarantee that every pair of cows is comparable (i.e., the ordering is complete).

The final formula for the answer is:

[ \text{Additional Comparisons} = \frac{N(N-1)}{2} - \text{(number of pairs that are already comparable)} ]

inputFormat

The first line contains two integers \(N\) and \(M\) separated by a space.

Each of the next \(M\) lines contains two integers \(X\) and \(Y\) representing a known comparison (i.e., cow \(X\) produces more milk than cow \(Y\)).

It is guaranteed that \(1 \le N \le 10^3\) and \(1 \le M \le 10^4\).

outputFormat

Output a single integer, which is the minimum number of additional comparisons required to fully determine the ordering of the cows.

sample

3 2
1 2
2 3

0