一场足球联赛最近在美丽的土地上开始了。有 $$$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)$$$。