Olet JOI-sanomalehden toimittaja ja vastaat urheilu-uutisista.

Eiliseen mennessä Kroatiassa pelattiin $n$ jalkapallojoukkueen välinen yksinkertainen sarja, jossa kaikki pelasivat kaikkia vastaan. Turnauksen järjestelytoimikunta on ilmeisesti asettanut joukkueet paremmuusjärjestykseen sijalta $1$ sijalle $n$ ottelutulosten ja sääntöjen perusteella. Osan otteluista voitto-/tappiotulosten lisäksi sinulle kerrottiin seuraavat tiedot:

• Tieto $1$: Yhtäkään tasapeliä ei pelattu.
• Tieto $2$: Kaikki joukkueet saivat eri sijoituksen.
• Tieto $3$: Kaikilla $1 \le a < b \le n$ sijalla $a$ olevan joukkueen ja sijalla $b$ olevan joukkueen välisessä ottelussa voitti aina sijalla $a$ oleva joukkue.

Artikkelin kirjoittamista varten päätit päätellä sarjataulukon osasta otteluita saatujen tulosten sekä sinulle kerrottujen Tietojen $1$–$3$ perusteella.

Kirjoita ohjelma, joka syötteenä annettujen ottelutulosten perusteella tulostaa $1$ kerrottuihin tietoihin sopivan sarjataulukon. Selvitä myös, onko tulostetun sarjataulukon lisäksi olemassa muita kerrottuihin tietoihin sopivia sarjataulukoita.

Tässä sarjataulukolla tarkoitetaan joukkueiden luetteloa järjestettynä sijasta $1$ sijaan $n$.

Esimerkit

Esimerkki 1 (Tapaus, jossa tietoihin sopivia sarjataulukoita on vain $1$)

Oletetaan, että joukkueita on $4$, joukkueet on numeroitu luvuin $1$–$4$ ja otteluiden tulokset on annettu seuraavassa taulukossa.

Kun rivillä $i$ ja sarakkeessa $j$ on $\circ$, se tarkoittaa, että joukkueen numero $i$ ja joukkueen numero $j$ välisessä ottelussa voitti joukkue numero $i$. Kun siinä on $\times$, se tarkoittaa, että joukkue numero $j$ voitti. $?$ tarkoittaa, että ottelun tulosta ei ole annettu.

Tällöin kerrottuihin tietoihin sopivia sarjataulukoita on vain seuraava $1$:

• $1$. sija: joukkue numero $3$
• $2$. sija: joukkue numero $4$
• $3$. sija: joukkue numero $1$
• $4$. sija: joukkue numero $2$

Esimerkki 2 (Tapaus, jossa tietoihin sopivia sarjataulukoita on useita)

Oletetaan, että joukkueita on $3$, joukkueet on numeroitu luvuin $1$–$3$ ja otteluiden tulokset on annettu seuraavassa taulukossa.

Tällöin kerrottuihin tietoihin sopivia sarjataulukoita ovat seuraavat $2$:

• $1$. sija: joukkue numero $2$, $2$. sija: joukkue numero $1$, $3$. sija: joukkue numero $3$
• $1$. sija: joukkue numero $2$, $2$. sija: joukkue numero $3$, $3$. sija: joukkue numero $1$

Syöte

Rivillä $1$ on jalkapallojoukkueiden lukumäärä $n$. Joukkueet on numeroitu luvuin $1$–$n$.

Rivillä $2$ on annettujen ottelutulosten lukumäärä $m$.

Riveillä $3$–$m + 2$ annetaan otteluiden tulokset. Kukin rivi sisältää $2$ välilyönnillä erotettua kokonaislukua $i, j$ ja ilmaisee, että joukkue numero $i$ voitti joukkueen numero $j$.

Luvut $n, m$ toteuttavat ehdot $1 \le n \le 5000$, $1 \le m \le 100000$.

Arvostelussa käytettävästä testiaineistosta $30\%$ täyttää ehdot $1 \le n \le 7$, $1 \le m \le 15$. Lisäksi $60\%$ täyttää ehdot $1 \le n \le 100$, $1 \le m \le 2000$.

Tuloste

Tuloste koostuu $n + 1$ rivistä.

Tulosta $n$ ensimmäiselle riville (riveille $1$–$n$) kerrottuihin tietoihin sopiva sarjataulukko. Tulosta riville $i$ ($1 \le i \le n$) sijalle $i$ sijoittuneen joukkueen numero.

Tulosta riville $n + 1$ kokonaisluku, joka ilmaisee, onko tulostetun sarjataulukon lisäksi olemassa muita kerrottuihin tietoihin sopivia sarjataulukoita: jos ei ole, tulosta $0$, ja jos on, tulosta $1$.

Esimerkit syötteestä ja tulosteesta

Esimerkkisyöte 1

Esimerkkiä $1$ vastaavat syöte ja tuloste ovat seuraavat.

4
5
1 2
3 1
3 2
3 4
4 1

Esimerkkituloste 1

3
4
1
2
0

Esimerkkisyöte 2

Esimerkkiä $2$ vastaava syöte on seuraava.

3
2
2 1
2 3

Tälle syötteelle ovat mahdollisia seuraavat $2$ tulostetta; kumman tahansa tulostaminen hyväksytään.

Esimerkkituloste 2

2
1
3
1

2
3
1
1