Du bist Reporter bei der JOI-Zeitung und für Sportartikel zuständig.
Bis gestern fand in Kroatien ein Rundenturnier (Jeder-gegen-jeden-Turnier) mit $n$ Fußballmannschaften statt. Das Organisationskomitee des Turniers hat offenbar jeder Mannschaft anhand der Spielergebnisse und des Reglements einen Rang vom $1$. Platz bis zum $n$. Platz zugewiesen. Zusammen mit den Sieg-/Niederlage-Ergebnissen einiger Spiele wurden dir folgende Informationen mitgeteilt:
- Information $1$: Es gab keine unentschiedenen Spiele.
- Information $2$: Alle Mannschaften erhielten unterschiedliche Ränge.
- Information $3$: Für alle $1 \le a < b \le n$ hat im Spiel zwischen der Mannschaft auf Platz $a$ und der Mannschaft auf Platz $b$ stets die Mannschaft auf Platz $a$ gewonnen.
Um deinen Artikel zu verfassen, hast du beschlossen, anhand der Ergebnisse einiger Spiele und der mitgeteilten Informationen $1$–$3$ auf die Rangliste zu schließen.
Schreibe ein Programm, das bei Eingabe der Ergebnisse einiger Spiele $1$ mit den mitgeteilten Informationen verträgliche Rangliste ausgibt. Bestimme außerdem, ob neben der ausgegebenen Rangliste noch eine weitere mit den mitgeteilten Informationen verträgliche Rangliste existiert.
Hierbei bezeichnet die Rangliste die Aufzählung der Mannschaften in der Reihenfolge vom $1$. Platz bis zum $n$. Platz.
Beispiele
Beispiel 1 (Wenn es nur $1$ mit den Informationen verträgliche Rangliste gibt)
Angenommen, die Anzahl der Mannschaften beträgt $4$, die Mannschaften sind von $1$ bis $4$ nummeriert, und die Spielergebnisse sind durch die folgende Tabelle gegeben.
| $i \backslash j$ | $1$ | $2$ | $3$ | $4$ |
|---|---|---|---|---|
| $1$ | $-$ | $\circ$ | $\times$ | $\times$ |
| $2$ | $\times$ | $-$ | $\times$ | $?$ |
| $3$ | $\circ$ | $\circ$ | $-$ | $\circ$ |
| $4$ | $\circ$ | $?$ | $\times$ | $-$ |
Wenn in Zeile $i$, Spalte $j$ ein $\circ$ steht, bedeutet dies, dass im Spiel zwischen Mannschaft Nummer $i$ und Mannschaft Nummer $j$ die Mannschaft Nummer $i$ gewonnen hat. Wenn dort ein $\times$ steht, bedeutet dies, dass Mannschaft Nummer $j$ gewonnen hat. $?$ bedeutet, dass das Spielergebnis nicht bekannt gegeben wurde.
In diesem Fall gibt es nur die folgende $1$ Rangliste, die mit den mitgeteilten Informationen verträglich ist:
- $1$. Platz: Mannschaft Nummer $3$
- $2$. Platz: Mannschaft Nummer $4$
- $3$. Platz: Mannschaft Nummer $1$
- $4$. Platz: Mannschaft Nummer $2$
Beispiel 2 (Wenn es mehrere mit den Informationen verträgliche Ranglisten gibt)
Angenommen, die Anzahl der Mannschaften beträgt $3$, die Mannschaften sind von $1$ bis $3$ nummeriert, und die Spielergebnisse sind durch die folgende Tabelle gegeben.
| $i \backslash j$ | $1$ | $2$ | $3$ |
|---|---|---|---|
| $1$ | $-$ | $\times$ | $?$ |
| $2$ | $\circ$ | $-$ | $\circ$ |
| $3$ | $?$ | $\times$ | $-$ |
In diesem Fall gibt es die folgenden $2$ Ranglisten, die mit den mitgeteilten Informationen verträglich sind:
- $1$. Platz: Mannschaft Nummer $2$, $2$. Platz: Mannschaft Nummer $1$, $3$. Platz: Mannschaft Nummer $3$
- $1$. Platz: Mannschaft Nummer $2$, $2$. Platz: Mannschaft Nummer $3$, $3$. Platz: Mannschaft Nummer $1$
Eingabe
In der $1$. Zeile steht die Anzahl $n$ der Fußballmannschaften. Jede Mannschaft ist von $1$ bis $n$ nummeriert.
In der $2$. Zeile steht die Anzahl $m$ der gegebenen Spielergebnisse.
Die $3$. Zeile bis zur Zeile $m + 2$ geben die Spielergebnisse an. Jede Zeile enthält $2$ durch ein Leerzeichen getrennte ganze Zahlen $i, j$ und gibt an, dass Mannschaft Nummer $i$ gegen Mannschaft Nummer $j$ gewonnen hat.
$n, m$ erfüllen $1 \le n \le 5000$, $1 \le m \le 100000$.
Von den bei der Bewertung verwendeten Testdaten erfüllen $30\%$ die Bedingung $1 \le n \le 7$, $1 \le m \le 15$. Weiterhin erfüllen $60\%$ die Bedingung $1 \le n \le 100$, $1 \le m \le 2000$.
Ausgabe
Die Ausgabe besteht aus $n + 1$ Zeilen.
Gib in den $n$ Zeilen von der $1$. Zeile bis zur $n$. Zeile eine mit den mitgeteilten Informationen verträgliche Rangliste aus. Gib in der $i$-ten Zeile ($1 \le i \le n$) die Nummer der Mannschaft auf dem $i$. Platz aus.
Gib in der Zeile $n + 1$ eine ganze Zahl aus, die angibt, ob außer der ausgegebenen Rangliste noch eine weitere mit den mitgeteilten Informationen verträgliche Rangliste existiert: Wenn keine existiert, gib $0$ aus; wenn eine existiert, gib $1$ aus.
Beispiele für Ein- und Ausgabe
Beispieleingabe 1
Die Ein- und Ausgabe zu Beispiel $1$ lauten wie folgt.
4 5 1 2 3 1 3 2 3 4 4 1
Beispielausgabe 1
3 4 1 2 0
Beispieleingabe 2
Die Eingabedaten zu Beispiel $2$ lauten wie folgt.
3 2 2 1 2 3
Für diese Eingabedaten kommen die folgenden $2$ Ausgabedaten in Betracht; es ist egal, welche davon ausgegeben wird.
Beispielausgabe 2
2 1 3 1
2 3 1 1