CF1264E Beautiful League

A football league has recently begun in Beautiful land. There are $ n $ teams participating in the league. Let's enumerate them with integers from $ 1 $ to $ n $ . There will be played exactly $ \frac{n(n-1)}{2} $ matches: each team will play against all other teams exactly once. In each match, there is always a winner and loser and there is no draw. After all matches are played, the organizers will count the number of beautiful triples. Let's call a triple of three teams $ (A, B, C) $ beautiful if a team $ A $ win against a team $ B $ , a team $ B $ win against a team $ C $ and a team $ C $ win against a team $ A $ . We look only to a triples of different teams and the order of teams in the triple is important. The beauty of the league is the number of beautiful triples. At the moment, $ m $ matches were played and their results are known. What is the maximum beauty of the league that can be, after playing all remaining matches? Also find a possible results for all remaining $ \frac{n(n-1)}{2} - m $ matches, so that the league has this maximum beauty.

N/A

N/A

The beauty of league in the first test case is equal to $ 3 $ because there exists three beautiful triples: $ (1, 2, 3) $ , $ (2, 3, 1) $ , $ (3, 1, 2) $ . The beauty of league in the second test is equal to $ 6 $ because there exists six beautiful triples: $ (1, 2, 4) $ , $ (2, 4, 1) $ , $ (4, 1, 2) $ , $ (2, 4, 3) $ , $ (4, 3, 2) $ , $ (3, 2, 4) $ .