Anda adalah seorang reporter surat kabar JOI yang bertanggung jawab atas artikel olahraga.
Hingga kemarin, di Kroasia telah diadakan pertandingan liga setengah kompetisi (round-robin) yang diikuti oleh $n$ tim sepak bola. Komite pelaksana turnamen tampaknya telah memberikan peringkat dari peringkat ke-$1$ hingga peringkat ke-$n$ kepada masing-masing tim berdasarkan hasil pertandingan dan peraturan. Bersama dengan hasil menang/kalah dari sebagian pertandingan, informasi berikut disampaikan kepada Anda:
- Informasi $1$: Tidak ada pertandingan yang berakhir seri.
- Informasi $2$: Setiap tim mendapatkan peringkat yang berbeda-beda.
- Informasi $3$: Untuk semua $1 \le a < b \le n$, dalam pertandingan antara tim peringkat ke-$a$ dan tim peringkat ke-$b$, tim peringkat ke-$a$ selalu menang.
Untuk menulis artikel, Anda memutuskan untuk memperkirakan tabel peringkat berdasarkan hasil menang/kalah dari sebagian pertandingan serta Informasi $1$–$3$ yang disampaikan.
Buatlah program yang, ketika diberikan masukan berupa hasil menang/kalah dari sebagian pertandingan, mengeluarkan $1$ tabel peringkat yang sesuai dengan informasi yang disampaikan. Selain itu, tentukan pula apakah terdapat tabel peringkat lain yang sesuai dengan informasi yang disampaikan selain tabel peringkat yang dikeluarkan.
Di sini, tabel peringkat berarti urutan tim yang disusun mulai dari peringkat ke-$1$ hingga peringkat ke-$n$.
Contoh
Contoh 1 (Ketika hanya ada $1$ tabel peringkat yang sesuai dengan informasi)
Misalkan banyaknya tim adalah $4$, setiap tim diberi nomor dari $1$ sampai $4$, dan hasil menang/kalah diberikan oleh tabel berikut.
| $i \backslash j$ | $1$ | $2$ | $3$ | $4$ |
|---|---|---|---|---|
| $1$ | $-$ | $\circ$ | $\times$ | $\times$ |
| $2$ | $\times$ | $-$ | $\times$ | $?$ |
| $3$ | $\circ$ | $\circ$ | $-$ | $\circ$ |
| $4$ | $\circ$ | $?$ | $\times$ | $-$ |
Ketika baris ke-$i$ kolom ke-$j$ berisi $\circ$, artinya pada pertandingan antara tim bernomor $i$ dan tim bernomor $j$, tim bernomor $i$ menang. Ketika berisi $\times$, artinya tim bernomor $j$ menang. $?$ berarti hasil menang/kalah tidak diberikan.
Dalam kasus ini, hanya ada $1$ tabel peringkat yang sesuai dengan informasi yang disampaikan, yaitu sebagai berikut:
- Peringkat ke-$1$: Tim nomor $3$
- Peringkat ke-$2$: Tim nomor $4$
- Peringkat ke-$3$: Tim nomor $1$
- Peringkat ke-$4$: Tim nomor $2$
Contoh 2 (Ketika ada beberapa tabel peringkat yang sesuai dengan informasi)
Misalkan banyaknya tim adalah $3$, setiap tim diberi nomor dari $1$ sampai $3$, dan hasil menang/kalah diberikan oleh tabel berikut.
| $i \backslash j$ | $1$ | $2$ | $3$ |
|---|---|---|---|
| $1$ | $-$ | $\times$ | $?$ |
| $2$ | $\circ$ | $-$ | $\circ$ |
| $3$ | $?$ | $\times$ | $-$ |
Dalam kasus ini, ada $2$ tabel peringkat yang sesuai dengan informasi yang disampaikan, yaitu sebagai berikut:
- Peringkat ke-$1$: Tim nomor $2$, Peringkat ke-$2$: Tim nomor $1$, Peringkat ke-$3$: Tim nomor $3$
- Peringkat ke-$1$: Tim nomor $2$, Peringkat ke-$2$: Tim nomor $3$, Peringkat ke-$3$: Tim nomor $1$
Masukan
Baris ke-$1$ berisi banyaknya tim sepak bola $n$. Setiap tim diberi nomor dari $1$ sampai $n$.
Baris ke-$2$ berisi banyaknya hasil menang/kalah pertandingan yang diberikan, yaitu $m$.
Baris ke-$3$ hingga baris ke-$m + 2$ menyatakan hasil menang/kalah pertandingan. Setiap baris memuat $2$ bilangan bulat $i, j$ yang dipisahkan oleh spasi, yang menyatakan bahwa tim bernomor $i$ menang melawan tim bernomor $j$.
$n, m$ memenuhi $1 \le n \le 5000$, $1 \le m \le 100000$.
Dari data uji yang digunakan saat penilaian, $30\%$ memenuhi $1 \le n \le 7$, $1 \le m \le 15$. Selain itu, $60\%$ memenuhi $1 \le n \le 100$, $1 \le m \le 2000$.
Keluaran
Keluaran terdiri dari $n + 1$ baris.
Pada $n$ baris mulai dari baris ke-$1$ hingga baris ke-$n$, keluarkan tabel peringkat yang sesuai dengan informasi yang disampaikan. Pada baris ke-$i$ ($1 \le i \le n$), keluarkan nomor tim yang berada di peringkat ke-$i$.
Pada baris ke-$n + 1$, keluarkan sebuah bilangan bulat yang menyatakan apakah ada tabel peringkat lain yang sesuai dengan informasi yang disampaikan selain tabel peringkat yang dikeluarkan: keluarkan $0$ jika tidak ada, dan keluarkan $1$ jika ada.
Contoh Masukan dan Keluaran
Contoh Masukan 1
Masukan dan keluaran yang sesuai dengan Contoh $1$ adalah sebagai berikut.
4 5 1 2 3 1 3 2 3 4 4 1
Contoh Keluaran 1
3 4 1 2 0
Contoh Masukan 2
Data masukan yang sesuai dengan Contoh $2$ adalah sebagai berikut.
3 2 2 1 2 3
Terhadap data masukan ini, terdapat $2$ kemungkinan data keluaran berikut; mengeluarkan yang mana saja diperbolehkan.
Contoh Keluaran 2
2 1 3 1
2 3 1 1