Sei un giornalista del quotidiano JOI e ti occupi degli articoli sportivi.
Fino a ieri, in Croazia si è svolto un torneo a girone all'italiana tra $n$ squadre di calcio. Il comitato organizzatore del torneo sembra aver assegnato a ciascuna squadra una posizione in classifica dal $1$^o posto all'$n$-esimo posto in base ai risultati delle partite e al regolamento. Insieme ai risultati (vittoria o sconfitta) di alcune partite, ti sono state riferite le seguenti informazioni:
- Informazione $1$: Non ci sono state partite terminate in pareggio.
- Informazione $2$: A tutte le squadre sono state assegnate posizioni diverse.
- Informazione $3$: Per tutti gli $1 \le a < b \le n$, nella partita tra la squadra al posto $a$ e la squadra al posto $b$, ha sempre vinto la squadra al posto $a$.
Per scrivere il tuo articolo, hai deciso di dedurre la classifica sulla base dei risultati di alcune partite e delle Informazioni $1$–$3$ che ti sono state riferite.
Scrivi un programma che, ricevuti in input i risultati di alcune partite, stampi $1$ classifica compatibile con le informazioni riferite. Determina inoltre se, oltre alla classifica stampata, esista o meno un'altra classifica compatibile con le informazioni riferite.
Qui, per classifica si intende l'elenco delle squadre ordinate dal $1$^o posto all'$n$-esimo posto.
Esempi
Esempio 1 (Caso in cui esiste $1$ sola classifica compatibile con le informazioni)
Supponiamo che il numero di squadre sia $4$, che le squadre siano numerate da $1$ a $4$ e che i risultati delle partite siano dati dalla seguente tabella.
| $i \backslash j$ | $1$ | $2$ | $3$ | $4$ |
|---|---|---|---|---|
| $1$ | $-$ | $\circ$ | $\times$ | $\times$ |
| $2$ | $\times$ | $-$ | $\times$ | $?$ |
| $3$ | $\circ$ | $\circ$ | $-$ | $\circ$ |
| $4$ | $\circ$ | $?$ | $\times$ | $-$ |
Quando la riga $i$, colonna $j$ è $\circ$, significa che nella partita tra la squadra numero $i$ e la squadra numero $j$ ha vinto la squadra numero $i$. Quando è $\times$, significa che ha vinto la squadra numero $j$. $?$ significa che il risultato non è stato fornito.
In questo caso, esiste $1$ sola classifica compatibile con le informazioni riferite, ed è la seguente:
- $1$^o posto: squadra numero $3$
- $2$^o posto: squadra numero $4$
- $3$^o posto: squadra numero $1$
- $4$^o posto: squadra numero $2$
Esempio 2 (Caso in cui esistono più classifiche compatibili con le informazioni)
Supponiamo che il numero di squadre sia $3$, che le squadre siano numerate da $1$ a $3$ e che i risultati delle partite siano dati dalla seguente tabella.
| $i \backslash j$ | $1$ | $2$ | $3$ |
|---|---|---|---|
| $1$ | $-$ | $\times$ | $?$ |
| $2$ | $\circ$ | $-$ | $\circ$ |
| $3$ | $?$ | $\times$ | $-$ |
In questo caso, esistono $2$ classifiche compatibili con le informazioni riferite, e sono le seguenti:
- $1$^o posto: squadra numero $2$, $2$^o posto: squadra numero $1$, $3$^o posto: squadra numero $3$
- $1$^o posto: squadra numero $2$, $2$^o posto: squadra numero $3$, $3$^o posto: squadra numero $1$
Input
Nella $1$-a riga è scritto il numero $n$ delle squadre di calcio. A ciascuna squadra è assegnato un numero da $1$ a $n$.
Nella $2$-a riga è scritto il numero $m$ dei risultati delle partite forniti.
Dalla $3$-a riga alla riga $m + 2$ sono rappresentati i risultati delle partite. Ciascuna riga contiene $2$ interi $i, j$ separati da uno spazio, e indica che la squadra numero $i$ ha sconfitto la squadra numero $j$.
$n, m$ soddisfano $1 \le n \le 5000$, $1 \le m \le 100000$.
Tra i dati di test utilizzati per la valutazione, il $30\%$ soddisfa $1 \le n \le 7$, $1 \le m \le 15$. Inoltre, il $60\%$ soddisfa $1 \le n \le 100$, $1 \le m \le 2000$.
Output
L'output è costituito da $n + 1$ righe.
Nelle $n$ righe dalla $1$-a riga all'$n$-esima riga, stampa una classifica compatibile con le informazioni riferite. Nell'$i$-esima riga ($1 \le i \le n$), stampa il numero della squadra classificata all'$i$-esimo posto.
Nella riga $n + 1$, stampa un intero che indichi se, oltre alla classifica stampata, esista o meno un'altra classifica compatibile con le informazioni riferite: se non esiste, stampa $0$; se esiste, stampa $1$.
Esempi di input e output
Input di esempio 1
L'input e l'output corrispondenti all'Esempio $1$ sono i seguenti.
4 5 1 2 3 1 3 2 3 4 4 1
Output di esempio 1
3 4 1 2 0
Input di esempio 2
I dati di input corrispondenti all'Esempio $2$ sono i seguenti.
3 2 2 1 2 3
Per questi dati di input sono possibili i seguenti $2$ dati di output; è consentito stampare indifferentemente l'uno o l'altro.
Output di esempio 2
2 1 3 1
2 3 1 1