Vous êtes journaliste pour le journal JOI et êtes responsable de la rubrique sportive.
Jusqu'à hier s'est déroulé en Croatie un tournoi toutes rondes opposant $n$ équipes de football. Le comité d'organisation du tournoi semble avoir attribué à chaque équipe un rang allant de la $1$-re place à la $n$-ième place en fonction des résultats des matchs et du règlement. En plus des résultats (victoire ou défaite) d'une partie des matchs, les informations suivantes vous ont été communiquées :
- Information $1$ : Il n'y a eu aucun match nul.
- Information $2$ : Toutes les équipes ont obtenu un rang différent.
- Information $3$ : Pour tous $1 \le a < b \le n$, lors du match entre l'équipe classée $a$-ième et l'équipe classée $b$-ième, c'est toujours l'équipe classée $a$-ième qui l'a emporté.
Pour rédiger votre article, vous avez décidé de déduire le classement à partir des résultats d'une partie des matchs et des Informations $1$ à $3$ qui vous ont été communiquées.
Écrivez un programme qui, étant donné en entrée les résultats d'une partie des matchs, affiche $1$ classement compatible avec les informations communiquées. Déterminez également s'il existe ou non un autre classement compatible avec les informations communiquées en dehors du classement affiché.
Ici, on appelle classement la liste des équipes ordonnées de la $1$-re place à la $n$-ième place.
Exemples
Exemple 1 (Cas où il n'existe qu'un seul ($1$) classement compatible avec les informations)
Supposons qu'il y ait $4$ équipes, numérotées de $1$ à $4$, et que les résultats des matchs soient donnés par le tableau suivant.
| $i \backslash j$ | $1$ | $2$ | $3$ | $4$ |
|---|---|---|---|---|
| $1$ | $-$ | $\circ$ | $\times$ | $\times$ |
| $2$ | $\times$ | $-$ | $\times$ | $?$ |
| $3$ | $\circ$ | $\circ$ | $-$ | $\circ$ |
| $4$ | $\circ$ | $?$ | $\times$ | $-$ |
Lorsque la case à la ligne $i$ et à la colonne $j$ contient $\circ$, cela signifie que lors du match entre l'équipe numéro $i$ et l'équipe numéro $j$, l'équipe numéro $i$ a gagné. Lorsqu'elle contient $\times$, cela signifie que l'équipe numéro $j$ a gagné. $?$ signifie que le résultat du match n'est pas donné.
Dans ce cas, il n'existe qu'un seul ($1$) classement compatible avec les informations communiquées, qui est le suivant :
- $1$-re place : équipe numéro $3$
- $2$-e place : équipe numéro $4$
- $3$-e place : équipe numéro $1$
- $4$-e place : équipe numéro $2$
Exemple 2 (Cas où il existe plusieurs classements compatibles avec les informations)
Supposons qu'il y ait $3$ équipes, numérotées de $1$ à $3$, et que les résultats des matchs soient donnés par le tableau suivant.
| $i \backslash j$ | $1$ | $2$ | $3$ |
|---|---|---|---|
| $1$ | $-$ | $\times$ | $?$ |
| $2$ | $\circ$ | $-$ | $\circ$ |
| $3$ | $?$ | $\times$ | $-$ |
Dans ce cas, il existe $2$ classements compatibles avec les informations communiquées, qui sont les suivants :
- $1$-re place : équipe numéro $2$, $2$-e place : équipe numéro $1$, $3$-e place : équipe numéro $3$
- $1$-re place : équipe numéro $2$, $2$-e place : équipe numéro $3$, $3$-e place : équipe numéro $1$
Entrée
La $1$-re ligne contient le nombre $n$ d'équipes de football. Chaque équipe est numérotée de $1$ à $n$.
La $2$-e ligne contient le nombre $m$ de résultats de matchs donnés.
Les lignes $3$ à $m + 2$ représentent les résultats des matchs. Chaque ligne contient $2$ entiers $i, j$ séparés par un espace, indiquant que l'équipe numéro $i$ a battu l'équipe numéro $j$.
$n, m$ vérifient $1 \le n \le 5000$, $1 \le m \le 100000$.
Parmi les données de test utilisées pour la notation, $30\%$ satisfont $1 \le n \le 7$, $1 \le m \le 15$. De plus, $60\%$ satisfont $1 \le n \le 100$, $1 \le m \le 2000$.
Sortie
La sortie est composée de $n + 1$ lignes.
Sur les $n$ lignes allant de la $1$-re ligne à la $n$-ième ligne, affichez un classement compatible avec les informations communiquées. Sur la $i$-ème ligne ($1 \le i \le n$), affichez le numéro de l'équipe classée $i$-ième.
Sur la ligne $n + 1$, affichez un entier indiquant s'il existe un autre classement compatible avec les informations communiquées en dehors du classement affiché : s'il n'en existe pas, affichez $0$ ; s'il en existe, affichez $1$.
Exemples d'entrée et de sortie
Exemple d'entrée 1
L'entrée et la sortie correspondant à l'Exemple $1$ sont les suivantes.
4 5 1 2 3 1 3 2 3 4 4 1
Exemple de sortie 1
3 4 1 2 0
Exemple d'entrée 2
Les données d'entrée correspondant à l'Exemple $2$ sont les suivantes.
3 2 2 1 2 3
Pour ces données d'entrée, les $2$ données de sortie suivantes sont envisageables ; vous pouvez afficher l'une ou l'autre.
Exemple de sortie 2
2 1 3 1
2 3 1 1