Ви — репортер газети 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$-му рядку та $j$-му стовпці стоїть $\circ$, це означає, що в матчі між командою номер $i$ та командою номер $j$ перемогла команда номер $i$. Якщо ж стоїть $\times$, це означає, що перемогла команда номер $j$. Символ $?$ означає, що результат матчу не вказано.

У цьому разі існує лише $1$ турнірна таблиця, що узгоджується з переданою інформацією:

• $1$-ше місце: команда номер $3$
• $2$-ге місце: команда номер $4$
• $3$-тє місце: команда номер $1$
• $4$-те місце: команда номер $2$

Приклад 2 (Випадок, коли існує декілька турнірних таблиць, що узгоджуються з інформацією)

Нехай кількість команд дорівнює $3$, команди пронумеровано від $1$ до $3$, а результати матчів задано такою таблицею.

У цьому разі існують $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