Вы — репортёр газеты JOI, отвечающий за спортивные статьи.
К вчерашнему дню в Хорватии прошёл круговой турнир с участием $n$ футбольных команд. По всей видимости, оргкомитет турнира на основе результатов матчей и регламента распределил команды по местам с $1$-го по $n$-е. Вместе с исходами (победа или поражение) некоторых матчей вам была передана следующая информация:
- Информация $1$: Матчей, завершившихся вничью, не было.
- Информация $2$: Все команды получили различные места.
- Информация $3$: Для всех $1 \le a < b \le n$ в матче между командой, занявшей $a$-е место, и командой, занявшей $b$-е место, обязательно побеждала команда, занявшая $a$-е место.
Чтобы написать статью, вы решили восстановить турнирную таблицу на основе исходов некоторых матчей и переданной вам Информации $1$–$3$.
Напишите программу, которая по заданным во входных данных исходам некоторых матчей выводит $1$ турнирную таблицу, согласующуюся с переданной информацией. Кроме того, определите, существует ли помимо выведенной турнирной таблицы какая-либо другая турнирная таблица, согласующаяся с переданной информацией.
Здесь под турнирной таблицей понимается список команд, упорядоченный от $1$-го места до $n$-го места.
Примеры
Пример 1 (Случай, когда существует только $1$ турнирная таблица, согласующаяся с информацией)
Пусть число команд равно $4$, команды пронумерованы от $1$ до $4$, а исходы матчей заданы следующей таблицей.
| $i \backslash j$ | $1$ | $2$ | $3$ | $4$ |
|---|---|---|---|---|
| $1$ | $-$ | $\circ$ | $\times$ | $\times$ |
| $2$ | $\times$ | $-$ | $\times$ | $?$ |
| $3$ | $\circ$ | $\circ$ | $-$ | $\circ$ |
| $4$ | $\circ$ | $?$ | $\times$ | $-$ |
Если в $i$-й строке и $j$-м столбце стоит $\circ$, это означает, что в матче между командой номер $i$ и командой номер $j$ победила команда номер $i$. Если же стоит $\times$, это означает, что победила команда номер $j$. Символ $?$ означает, что исход матча не задан.
В этом случае существует только $1$ турнирная таблица, согласующаяся с переданной информацией:
- $1$-е место: команда номер $3$
- $2$-е место: команда номер $4$
- $3$-е место: команда номер $1$
- $4$-е место: команда номер $2$
Пример 2 (Случай, когда существует несколько турнирных таблиц, согласующихся с информацией)
Пусть число команд равно $3$, команды пронумерованы от $1$ до $3$, а исходы матчей заданы следующей таблицей.
| $i \backslash j$ | $1$ | $2$ | $3$ |
|---|---|---|---|
| $1$ | $-$ | $\times$ | $?$ |
| $2$ | $\circ$ | $-$ | $\circ$ |
| $3$ | $?$ | $\times$ | $-$ |
В этом случае существуют $2$ турнирные таблицы, согласующиеся с переданной информацией:
- $1$-е место: команда номер $2$, $2$-е место: команда номер $1$, $3$-е место: команда номер $3$
- $1$-е место: команда номер $2$, $2$-е место: команда номер $3$, $3$-е место: команда номер $1$
Входные данные
В $1$-й строке записано количество футбольных команд $n$. Каждой команде присвоен номер от $1$ до $n$.
Во $2$-й строке записано количество известных исходов матчей $m$.
Строки с $3$-й по $m + 2$-ю описывают исходы матчей. Каждая строка содержит $2$ разделённых пробелом целых числа $i, j$ и означает, что команда номер $i$ победила команду номер $j$.
$n, m$ удовлетворяют условиям $1 \le n \le 5000$, $1 \le m \le 100000$.
Среди тестовых данных, используемых при проверке, $30\%$ удовлетворяют условиям $1 \le n \le 7$, $1 \le m \le 15$. Кроме того, $60\%$ удовлетворяют условиям $1 \le n \le 100$, $1 \le m \le 2000$.
Выходные данные
Выходные данные состоят из $n + 1$ строк.
В $n$ строках с $1$-й по $n$-ю выведите турнирную таблицу, согласующуюся с переданной информацией. В $i$-й строке ($1 \le i \le n$) выведите номер команды, занявшей $i$-е место.
В строке $n + 1$ выведите целое число, указывающее, существует ли кроме выведенной турнирной таблицы другая турнирная таблица, согласующаяся с переданной информацией: если не существует, выведите $0$, а если существует — выведите $1$.
Примеры входных и выходных данных
Пример ввода 1
Входные и выходные данные, соответствующие Примеру $1$, приведены ниже.
4 5 1 2 3 1 3 2 3 4 4 1
Пример вывода 1
3 4 1 2 0
Пример ввода 2
Входные данные, соответствующие Примеру $2$, приведены ниже.
3 2 2 1 2 3
Для этих входных данных возможны следующие $2$ варианта выходных данных; можно вывести любой из них.
Пример вывода 2
2 1 3 1
2 3 1 1