Eres periodista del periódico JOI y estás a cargo de los artículos deportivos.
Hasta ayer, en Croacia se celebró un torneo de liga de todos contra todos entre $n$ equipos de fútbol. Al parecer, el comité organizador del torneo asignó a cada equipo un puesto desde el $1$.º hasta el $n$-ésimo basándose en los resultados de los partidos y en el reglamento. Junto con el resultado de victoria o derrota de algunos de los partidos, se te transmitió la siguiente información:
- Información $1$: No hubo partidos empatados.
- Información $2$: Todos los equipos obtuvieron puestos diferentes.
- Información $3$: Para todo $1 \le a < b \le n$, en el partido entre el equipo en el puesto $a$ y el equipo en el puesto $b$, siempre ganó el equipo en el puesto $a$.
Para redactar tu artículo, decidiste deducir la tabla de clasificación a partir de los resultados de algunos de los partidos y de las Informaciones $1$ a $3$ transmitidas.
Escribe un programa que, dados como entrada los resultados de algunos de los partidos, imprima $1$ tabla de clasificación compatible con la información transmitida. Además, determina si existe alguna otra tabla de clasificación compatible con la información transmitida aparte de la tabla de clasificación impresa.
Aquí, por tabla de clasificación se entiende la lista de los equipos ordenados desde el $1$.º hasta el $n$-ésimo puesto.
Ejemplos
Ejemplo 1 (Cuando solo hay $1$ tabla de clasificación compatible con la información)
Supongamos que el número de equipos es $4$, que cada equipo tiene asignado un número del $1$ al $4$, y que los resultados vienen dados por la siguiente tabla.
| $i \backslash j$ | $1$ | $2$ | $3$ | $4$ |
|---|---|---|---|---|
| $1$ | $-$ | $\circ$ | $\times$ | $\times$ |
| $2$ | $\times$ | $-$ | $\times$ | $?$ |
| $3$ | $\circ$ | $\circ$ | $-$ | $\circ$ |
| $4$ | $\circ$ | $?$ | $\times$ | $-$ |
Cuando la fila $i$, columna $j$ es $\circ$, significa que en el partido entre el equipo número $i$ y el equipo número $j$, ganó el equipo número $i$. Cuando es $\times$, significa que ganó el equipo número $j$. $?$ significa que no se ha dado el resultado del partido.
En este caso, solo hay $1$ tabla de clasificación compatible con la información transmitida, que es la siguiente:
- $1$.º puesto: Equipo número $3$
- $2$.º puesto: Equipo número $4$
- $3$.º puesto: Equipo número $1$
- $4$.º puesto: Equipo número $2$
Ejemplo 2 (Cuando existen varias tablas de clasificación compatibles con la información)
Supongamos que el número de equipos es $3$, que cada equipo tiene asignado un número del $1$ al $3$, y que los resultados vienen dados por la siguiente tabla.
| $i \backslash j$ | $1$ | $2$ | $3$ |
|---|---|---|---|
| $1$ | $-$ | $\times$ | $?$ |
| $2$ | $\circ$ | $-$ | $\circ$ |
| $3$ | $?$ | $\times$ | $-$ |
En este caso, hay $2$ tablas de clasificación compatibles con la información transmitida, que son las siguientes:
- $1$.º puesto: Equipo número $2$, $2$.º puesto: Equipo número $1$, $3$.º puesto: Equipo número $3$
- $1$.º puesto: Equipo número $2$, $2$.º puesto: Equipo número $3$, $3$.º puesto: Equipo número $1$
Entrada
En la $1$.ª línea está escrito el número de equipos de fútbol $n$. A cada equipo se le asigna un número del $1$ al $n$.
En la $2$.ª línea está escrito el número de resultados de partidos dados $m$.
Desde la $3$.ª línea hasta la línea $m + 2$ se representan los resultados de los partidos. Cada línea contiene $2$ enteros $i, j$ separados por un espacio, lo que indica que el equipo número $i$ venció al equipo número $j$.
$n, m$ satisfacen $1 \le n \le 5000$, $1 \le m \le 100000$.
Entre los datos de prueba utilizados para la calificación, el $30\%$ satisface $1 \le n \le 7$, $1 \le m \le 15$. Asimismo, el $60\%$ satisface $1 \le n \le 100$, $1 \le m \le 2000$.
Salida
La salida consta de $n + 1$ líneas.
En las $n$ líneas desde la $1$.ª línea hasta la $n$-ésima línea, imprime una tabla de clasificación compatible con la información transmitida. En la $i$-ésima línea ($1 \le i \le n$), imprime el número del equipo en el puesto $i$.
En la línea $n + 1$, imprime un entero que indique si existe o no alguna otra tabla de clasificación compatible con la información transmitida aparte de la tabla de clasificación impresa: si no existe, imprime $0$; si existe, imprime $1$.
Ejemplos de entrada y salida
Ejemplo de entrada 1
La entrada y la salida correspondientes al Ejemplo $1$ son las siguientes.
4 5 1 2 3 1 3 2 3 4 4 1
Ejemplo de salida 1
3 4 1 2 0
Ejemplo de entrada 2
Los datos de entrada correspondientes al Ejemplo $2$ son los siguientes.
3 2 2 1 2 3
Para estos datos de entrada, se pueden considerar los siguientes $2$ datos de salida; se puede imprimir cualquiera de los dos.
Ejemplo de salida 2
2 1 3 1
2 3 1 1