Maximizing Cyclic Triples in a Tournament

Consider a round‐robin tournament among N players in which every pair of players plays exactly one match. In some matches the result has been determined already; in each such match one player beats the other. We say that an unordered triple (A, B, C) is a rock-paper-scissors triple (or cyclic triple) if one of the players beats a second, the second beats the third, and the third beats the first. (For example, if A beats B, B beats C, and C beats A then the triple is cyclic.) Note that the ordering in the triple is unimportant; the triples (A, B, C), (A, C, B), etc. are considered identical.

After some matches have been played, the remaining matches can have their results chosen arbitrarily. Your task is to determine, under an optimal assignment of outcomes for the remaining matches, the maximum possible number of cyclic triples that could be observed when the tournament is complete.

A key observation is that every unordered triple of players, when all matches among them are decided, is either transitive (one player wins both of its games, one loses both) or cyclic (each player wins exactly one game). In a complete tournament the number of cyclic triples equals

$$\text{cyclic} = \binom{N}{3} - \sum_{i=1}^N \binom{d_i}{2}, $$

where d_i is the outdegree (number of wins) of the i-th player. Some of the wins are fixed in the input; for the remaining free matches we can decide the winners. However, the decision must be consistent (each match is played exactly once). Choosing the outcomes for the free matches determines extra wins which add to the fixed wins. For each player i if we denote by x_i the number of free wins assigned to player i, then the contribution from player i to the transitive triples is

$$\binom{(\text{fixed}_i + x_i)}{2} = \frac{(\text{fixed}_i+ x_i)(\text{fixed}_i+ x_i-1)}{2}. $$

Your goal is to choose the winners for the free matches so that the total \( \sum_{i=1}^N \binom{(\text{fixed}_i+ x_i)}{2} \) is minimized, thereby maximizing the cyclic triples.

Input Format:
The first line contains two integers N and M (number of players and number of matches already completed). Each of the next M lines contains two integers u and v indicating that player u beat player v in a played match. (Players are numbered from 1 to N.)

Output Format:
Print a single integer, the maximum possible number of cyclic triples that can be achieved after assigning outcomes for all remaining matches optimally.

Note:
There will be a total of \(\frac{N(N-1)}{2}\) matches in the tournament. For every pair of players where the result is not fixed, you are free to choose the outcome. The challenge is that each free match decision contributes to the win counts for two players, and these decisions must be made consistently across the tournament.

Hint:
Observe that the number of cyclic triples is \(\binom{N}{3}\) minus the sum over players of \( \binom{d_i}{2} \). Since the fixed wins (\(\text{fixed}_i\)) are given, you must choose the outcomes for the free matches (which add an extra win to one of the two players in a match) so that the additional cost, \(\sum_i\Big(\text{fixed}_i \cdot x_i + \binom{x_i}{2}\Big)\), is minimized. This can be approached as a min cost flow problem where for each free match you decide to which player to assign the win.

inputFormat

The input begins with a line containing two integers N and M (1 ≤ N ≤ 50 for example, and 0 ≤ M ≤ N(N-1)/2). Each of the following M lines contains two integers u and v (1 ≤ u,v ≤ N, u != v) which means that player u has beaten player v in a match that has already been played.

It is guaranteed that every pair of players appears at most once in the input (in only one direction) and that the matches already played are consistent.

outputFormat

Output a single integer: the maximum possible number of cyclic triples (i.e. triples of players forming a rock-paper-scissors cycle) that can occur after all matches have been played.

sample

3 0

1

</p>