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$ 支球队参加该联赛。我们用从 $1$ 到 $n$ 的整数对它们进行编号。

总共将进行恰好 $\frac{n(n-1)}{2}$ 场比赛：每支队伍都将与其他所有队伍各交手一次。每场比赛必有胜者与负者，不存在平局。

所有比赛结束后，主办方将统计“优美三元组”的数量。我们称由三支不同队伍 $(A, B, C)$ 构成的三元组为优美三元组，当且仅当队伍 $A$ 战胜队伍 $B$、队伍 $B$ 战胜队伍 $C$、且队伍 $C$ 又战胜队伍 $A$。注意：我们只考虑由互不相同的三支队伍组成的三元组，且三元组中队伍的顺序是重要的（即 $(A,B,C)$ 与 $(B,C,A)$ 视为不同三元组，只要满足对应胜负关系）。

联赛的优美度即为优美三元组的总数。

目前，已有 $m$ 场比赛完成，其结果已知。

在剩余全部 $\frac{n(n-1)}{2} - m$ 场比赛的结果均可自由设定的前提下，联赛可能达到的最大优美度是多少？并请给出一组能使联赛达到该最大优美度的、所有剩余比赛的结果。

The first line contains two integers $n, m$ ($3 \leq n \leq 50, 0 \leq m \leq \frac{n(n-1)}{2}$) — the number of teams in the football league and the number of matches that were played.

Each of $m$ following lines contains two integers $u$ and $v$ ($1 \leq u, v \leq n$, $u \neq v$) denoting that the $u$-th team won against the $v$-th team. It is guaranteed that each unordered pair of teams appears at most once.

第一行包含两个整数 $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$ 支队伍。保证任意一对无序队伍至多出现一次。

Print $n$ lines, each line having a string of exactly $n$ characters. Each character must be either $0$ or $1$.

Let $a_{ij}$ be the $j$-th number in the $i$-th line. For all $1 \leq i \leq n$ it should be true, that $a_{ii} = 0$. For all pairs of teams $i \neq j$ the number $a_{ij}$ indicates the result of the match between the $i$-th team and the $j$-th team:

• If $a_{ij}$ is $1$, the $i$-th team wins against the $j$-th team;
• Otherwise the $j$-th team wins against the $i$-th team;
• Also, it should be true, that $a_{ij} + a_{ji} = 1$.

Also note that the results of the $m$ matches that were already played cannot be changed in your league.

The beauty of the league in the output should be maximum possible. If there are multiple possible answers with maximum beauty, you can print any of them.

输出 $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$ 支队伍；
• 否则（即 $a_{ij} = 0$），第 $j$ 支队伍战胜第 $i$ 支队伍；
• 此外，还需满足 $a_{ij} + a_{ji} = 1$。

还需注意：已进行的 $m$ 场比赛的结果在你的联赛中不可更改。

输出联赛的“美观度”应尽可能大。若存在多个美观度最大的可行解，输出任意一个即可。

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)$.

第一个测试用例中联赛的美丽值等于 $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)$。