Du er journalist i JOI-avisen og har ansvaret for sportsartikler.

Fram til i går ble det spilt en serie der alle møtte alle blant $n$ fotballag i Kroatia. Arrangementskomiteen ser ut til å ha gitt hvert lag en plassering fra $1$. plass til $n$. plass basert på kampresultatene og reglene. Sammen med resultatene (seier eller tap) fra noen av kampene, har du fått følgende informasjon:

• Informasjon $1$: Ingen kamper endte uavgjort.
• Informasjon $2$: Alle lagene fikk ulik plassering.
• Informasjon $3$: For alle $1 \le a < b \le n$ gjaldt det at i kampen mellom laget på $a$. plass og laget på $b$. plass, vant alltid laget på $a$. plass.

For å skrive artikkelen din bestemte du deg for å finne ut hvordan tabellen så ut, basert på resultatene fra noen av kampene og Informasjon $1$–$3$ som ble formidlet til deg.

Skriv et program som, gitt resultatene fra noen av kampene som inndata, skriver ut $1$ tabell som stemmer overens med den formidlede informasjonen. Avgjøre også om det, utenom den utskrevne tabellen, finnes noen annen tabell som stemmer overens med informasjonen.

Her betyr tabellen en liste over lagene ordnet i rekkefølge fra $1$. plass til $n$. plass.

Eksempler

Eksempel 1 (Når det bare finnes $1$ tabell som stemmer med informasjonen)

Anta at antall lag er $4$, at hvert lag er nummerert fra $1$ til $4$, og at kampresultatene er gitt ved følgende tabell.

Når rad $i$, kolonne $j$ er $\circ$, betyr det at lag nummer $i$ vant i kampen mellom lag nummer $i$ og lag nummer $j$. Når det står $\times$, betyr det at lag nummer $j$ vant. $?$ betyr at kampresultatet ikke er oppgitt.

I dette tilfellet finnes det bare $1$ tabell som stemmer overens med informasjonen, nemlig følgende:

• $1$. plass: lag nummer $3$
• $2$. plass: lag nummer $4$
• $3$. plass: lag nummer $1$
• $4$. plass: lag nummer $2$

Eksempel 2 (Når det finnes flere tabeller som stemmer med informasjonen)

Anta at antall lag er $3$, at hvert lag er nummerert fra $1$ til $3$, og at kampresultatene er gitt ved følgende tabell.

I dette tilfellet finnes det $2$ tabeller som stemmer overens med informasjonen, nemlig følgende:

• $1$. plass: lag nummer $2$, $2$. plass: lag nummer $1$, $3$. plass: lag nummer $3$
• $1$. plass: lag nummer $2$, $2$. plass: lag nummer $3$, $3$. plass: lag nummer $1$

Inndata

På den $1$. linjen står antallet fotballag $n$. Hvert lag er nummerert fra $1$ til $n$.

På den $2$. linjen står antallet oppgitte kampresultater $m$.

Fra den $3$. linjen til linje $m + 2$ oppgis kampresultatene. Hver linje inneholder $2$ heltall $i, j$ atskilt med mellomrom, som betyr at lag nummer $i$ vant over lag nummer $j$.

$n, m$ oppfyller $1 \le n \le 5000$, $1 \le m \le 100000$.

Blant testdataene som brukes under bedømmingen, oppfyller $30\%$ kravene $1 \le n \le 7$, $1 \le m \le 15$. Videre oppfyller $60\%$ kravene $1 \le n \le 100$, $1 \le m \le 2000$.

Utdata

Utdataene består av $n + 1$ linjer.

På de $n$ linjene fra linje $1$ til linje $n$ skal du skrive ut en tabell som stemmer overens med den formidlede informasjonen. På linje $i$ ($1 \le i \le n$) skal du skrive ut nummeret på laget på $i$. plass.

På linje $n + 1$ skal du skrive ut et heltall som angir om det finnes noen annen tabell som stemmer overens med informasjonen enn den som ble skrevet ut: hvis det ikke finnes noen, skriv ut $0$; hvis det finnes, skriv ut $1$.

Eksempler på inndata og utdata

Eksempelinndata 1

Inndata og utdata som tilsvarer Eksempel $1$, er som følger.

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

Eksempelutdata 1

3
4
1
2
0

Eksempelinndata 2

Inndataene som tilsvarer Eksempel $2$, er som følger.

3
2
2 1
2 3

For disse inndataene er følgende $2$ utdata mulige; du kan skrive ut hvilken som helst av dem.

Eksempelutdata 2

2
1
3
1

2
3
1
1