← 返回题目列表

Codeforces · 1264/E

E. 美丽联盟

中文机器翻译题面 查看原题

一场足球联赛最近在美丽的土地上开始了。有 $$$n$$$ 球队参加联赛。让我们用从 $$$1$$$ 到 $$$n$$$ 的整数来枚举它们。

将进行 $$$\frac{n(n-1)}{2}$$$ 比赛:每支球队将与所有其他球队进行一场比赛。每场比赛都会有胜负,不存在平局。

所有比赛结束后,主办方将统计漂亮三连冠的数量。如果一支队伍 $$$A$$$ 战胜了一支队伍 $$$B$$$,一支队伍 $$$B$$$ 战胜了一支队伍 $$$C$$$,一支队伍 $$$C$$$ 战胜了一支队伍 $$$A$$$,我们称三支队伍 $$$(A, B, C)$$$ 为美丽。我们只关注不同球队的三人组,三人组中球队的顺序很重要。

联盟的美妙之处在于美丽的三重奏的数量。

目前,已经进行了 $$$m$$$ 场比赛,结果已知晓。

在打完剩下的所有比赛之后,联赛最大的魅力是什么?还为所有剩余的 $$$\frac{n(n-1)}{2} - 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$$$ 场比赛的结果无法更改。

联盟的美丽在输出上应该是最大可能的。如果有多个可能的答案,并且最美观,您可以打印其中任何一个。

示例

输入 #1

3 1
1 2

输出 #1

010
001
100

输入 #2

4 2
1 2
1 3

输出 #2

0110
0001
0100
1010

注意

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