CF1264E Beautiful League

美丽之地最近开始了一项足球联赛。有 $n$ 支队伍参加联赛。我们用 $1$ 到 $n$ 的整数编号这些队伍。 联赛将进行恰好 $\frac{n(n-1)}{2}$ 场比赛：每支队伍与其他所有队伍各比赛一次。每场比赛必有一方获胜，另一方失败，不存在平局。 所有比赛结束后，组织者会统计“美丽三元组”的数量。我们称三支队伍 $(A, B, C)$ 构成一个美丽三元组，当且仅当队伍 $A$ 战胜队伍 $B$，队伍 $B$ 战胜队伍 $C$，队伍 $C$ 战胜队伍 $A$。我们只考虑三支不同的队伍组成的三元组，且三元组中队伍的顺序是重要的。 联赛的美丽值即为美丽三元组的数量。 目前已经进行了 $m$ 场比赛，且这些比赛的结果已知。 请你求出，在剩余的比赛全部结束后，联赛的最大可能美丽值是多少。同时，请给出一种可能的剩余比赛结果，使得联赛的美丽值达到最大。

第一行包含两个整数 $n, m$（$3 \leq n \leq 50, 0 \leq m \leq \frac{n(n-1)}{2}$）——足球联赛的队伍数和已进行的比赛场数。 接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$，$u \neq v$），表示第 $u$ 支队伍战胜了第 $v$ 支队伍。保证每对队伍的无序对最多只出现一次。

输出 $n$ 行，每行包含一个长度为 $n$ 的字符串。每个字符只能是 $0$ 或 $1$。 令 $a_{ij}$ 表示第 $i$ 行的第 $j$ 个字符。对于所有 $1 \leq i \leq n$，应满足 $a_{ii} = 0$。对于所有 $i \neq j$，$a_{ij}$ 表示第 $i$ 支队伍与第 $j$ 支队伍的比赛结果： - 如果 $a_{ij} = 1$，则第 $i$ 支队伍战胜第 $j$ 支队伍； - 否则，第 $j$ 支队伍战胜第 $i$ 支队伍； - 并且应满足 $a_{ij} + a_{ji} = 1$。 同时，已进行的 $m$ 场比赛的结果在你的输出中必须保持不变。 输出的联赛美丽值应为最大可能值。如果有多种方案都能达到最大美丽值，你可以输出其中任意一种。

第一个测试样例中，联赛的美丽值为 $3$，因为存在三个美丽三元组：$(1, 2, 3)$，$(2, 3, 1)$，$(3, 1, 2)$。 第二个测试样例中，联赛的美丽值为 $6$，因为存在六个美丽三元组：$(1, 2, 4)$，$(2, 4, 1)$，$(4, 1, 2)$，$(2, 4, 3)$，$(4, 3, 2)$，$(3, 2, 4)$。 由 ChatGPT 4.1 翻译