Þú ert blaðamaður hjá JOI-dagblaðinu og sérð um íþróttafréttir.
Fram til gærdagsins fór fram deildarkeppni í Króatíu þar sem $n$ knattspyrnulið kepptu öll við hvert annað. Mótsstjórnin virðist hafa raðað liðunum í sæti frá $1$. sæti til $n$-ta sætis á grundvelli úrslita leikjanna og reglugerðar. Ásamt úrslitum (sigri eða tapi) úr hluta leikjanna voru þér færðar eftirfarandi upplýsingar:
- Upplýsingar $1$: Enginn leikur endaði með jafntefli.
- Upplýsingar $2$: Öll liðin hlutu ólík sæti.
- Upplýsingar $3$: Fyrir öll $1 \le a < b \le n$ gilti að í leik milli liðsins í $a$-ta sæti og liðsins í $b$-ta sæti vann liðið í $a$-ta sæti alltaf.
Til að skrifa greinina ákvaðst þú að geta þér til um stöðutöfluna út frá úrslitum úr hluta leikjanna og Upplýsingum $1$–$3$ sem þér voru færðar.
Skrifaðu forrit sem tekur við úrslitum úr hluta leikjanna sem inntaki og prentar út $1$ stöðutöflu sem samræmist upplýsingunum. Ákvarðaðu einnig hvort til sé einhver önnur stöðutafla sem samræmist upplýsingunum auk þeirrar stöðutöflu sem prentuð var út.
Hér á stöðutafla við lista yfir liðin í röð frá $1$. sæti til $n$-ta sætis.
Dæmi
Dæmi 1 (Þegar aðeins $1$ stöðutafla samræmist upplýsingunum)
Gerum ráð fyrir að fjöldi liða sé $4$, að liðin séu númeruð frá $1$ til $4$ og að úrslit leikjanna séu gefin í eftirfarandi töflu.
| $i \backslash j$ | $1$ | $2$ | $3$ | $4$ |
|---|---|---|---|---|
| $1$ | $-$ | $\circ$ | $\times$ | $\times$ |
| $2$ | $\times$ | $-$ | $\times$ | $?$ |
| $3$ | $\circ$ | $\circ$ | $-$ | $\circ$ |
| $4$ | $\circ$ | $?$ | $\times$ | $-$ |
Þegar lína $i$, dálkur $j$ er $\circ$ þýðir það að í leik milli liðs númer $i$ og liðs númer $j$ vann lið númer $i$. Þegar þar stendur $\times$ þýðir það að lið númer $j$ vann. $?$ þýðir að úrslit leiksins eru ekki gefin.
Í þessu tilviki er aðeins $1$ stöðutafla sem samræmist upplýsingunum, og hún er eftirfarandi:
- $1$. sæti: lið númer $3$
- $2$. sæti: lið númer $4$
- $3$. sæti: lið númer $1$
- $4$. sæti: lið númer $2$
Dæmi 2 (Þegar fleiri en ein stöðutafla samræmast upplýsingunum)
Gerum ráð fyrir að fjöldi liða sé $3$, að liðin séu númeruð frá $1$ til $3$ og að úrslit leikjanna séu gefin í eftirfarandi töflu.
| $i \backslash j$ | $1$ | $2$ | $3$ |
|---|---|---|---|
| $1$ | $-$ | $\times$ | $?$ |
| $2$ | $\circ$ | $-$ | $\circ$ |
| $3$ | $?$ | $\times$ | $-$ |
Í þessu tilviki eru $2$ stöðutöflur sem samræmast upplýsingunum, og þær eru eftirfarandi:
- $1$. sæti: lið númer $2$, $2$. sæti: lið númer $1$, $3$. sæti: lið númer $3$
- $1$. sæti: lið númer $2$, $2$. sæti: lið númer $3$, $3$. sæti: lið númer $1$
Inntak
Í $1$. línu er fjöldi knattspyrnuliða $n$. Hvert lið er númerað frá $1$ til $n$.
Í $2$. línu er fjöldi gefinna úrslita leikja $m$.
Frá $3$. línu til línu $m + 2$ eru úrslit leikjanna gefin. Hver lína inniheldur $2$ heiltölur $i, j$ aðskildar með bili, sem táknar að lið númer $i$ vann lið númer $j$.
$n, m$ uppfylla $1 \le n \le 5000$, $1 \le m \le 100000$.
Meðal prófunargagna sem notuð eru við yfirferð uppfyllir $30\%$ skilyrðin $1 \le n \le 7$, $1 \le m \le 15$. Ennfremur uppfyllir $60\%$ skilyrðin $1 \le n \le 100$, $1 \le m \le 2000$.
Úttak
Úttakið samanstendur af $n + 1$ línum.
Í línunum $n$ frá $1$. línu til $n$-tu línu skaltu prenta út stöðutöflu sem samræmist upplýsingunum. Í $i$-tu línu ($1 \le i \le n$) skaltu prenta út númer liðsins í $i$-ta sæti.
Í línu $n + 1$ skaltu prenta út heiltölu sem gefur til kynna hvort til sé önnur stöðutafla sem samræmist upplýsingunum auk þeirrar sem prentuð var út: ef engin slík er til skaltu prenta $0$, en ef hún er til skaltu prenta $1$.
Dæmi um inntak og úttak
Dæmi um inntak 1
Inntak og úttak sem samsvara Dæmi $1$ eru sem hér segir.
4 5 1 2 3 1 3 2 3 4 4 1
Dæmi um úttak 1
3 4 1 2 0
Dæmi um inntak 2
Inntaksgögn sem samsvara Dæmi $2$ eru sem hér segir.
3 2 2 1 2 3
Fyrir þessi inntaksgögn koma eftirfarandi $2$ úttaksgögn til greina; hvort sem er má prenta út.
Dæmi um úttak 2
2 1 3 1
2 3 1 1