E. Красивая лига
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Футбольная лига недавно стартовала в Красивой долине. Всего $$$n$$$ команд участвует в этой лиге. Пронумеруем их для удобства целыми числами от $$$1$$$ до $$$n$$$.

Всего будет проведено ровно $$$\frac{n(n-1)}{2}$$$ матчей: каждая команда будет играть со всеми оставшимися командами ровно по одному разу. В каждом матче всегда есть победившая и проигравшая команда, ничьих не бывает.

После того, как все матчи будут сыграны, организаторы посчитают количество красивых троек. Тройка команд $$$(A, B, C)$$$ называется красивой, если команда $$$A$$$ победила команду $$$B$$$, команда $$$B$$$ победила команду $$$C$$$ и команда $$$C$$$ победила команду $$$A$$$. Мы рассматриваем только тройки различных команд, порядок команд внутри тройки имеет значение.

Красотой лиги назовем количество красивых троек.

В данный момент, $$$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}$$$ $$$j$$$-е число в $$$i$$$-й строке. Для всех $$$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
1 2
Выходные данные
010
001
100
Входные данные
4 2
1 2
1 3
Выходные данные
0110
0001
0100
1010
Примечание

Красота лиги в первом тесте равна $$$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)$$$.