Du är reporter på JOI-tidningen och ansvarar för sportartiklar.

Fram till igår spelades en serie där alla mötte alla mellan $n$ fotbollslag i Kroatien. Tävlingskommittén verkar ha rangordnat lagen från $1$:a plats till $n$:te plats baserat på matchresultaten och reglerna. Tillsammans med vinst- och förlustresultaten från en del av matcherna fick du följande information:

• Information $1$: Det förekom inga oavgjorda matcher.
• Information $2$: Alla lag fick olika placeringar.
• Information $3$: För alla $1 \le a < b \le n$ gällde att i matchen mellan laget på $a$:te plats och laget på $b$:te plats vann alltid laget på $a$:te plats.

För att skriva din artikel bestämde du dig för att lista ut resultatlistan utifrån resultaten i några av matcherna samt Information $1$–$3$ som du fått.

Skriv ett program som, givet resultaten från några av matcherna som indata, skriver ut $1$ resultatlista som stämmer överens med den givna informationen. Avgör också om det utöver den utskrivna resultatlistan finns någon annan resultatlista som stämmer överens med informationen.

Här avser resultatlistan en lista över lagen ordnade från $1$:a plats till $n$:te plats.

Exempel

Exempel 1 (När det bara finns $1$ resultatlista som stämmer överens med informationen)

Antag att antalet lag är $4$, att lagen är numrerade från $1$ till $4$ och att matchresultaten ges av följande tabell.

När rad $i$, kolumn $j$ är $\circ$ betyder det att i matchen mellan lag nummer $i$ och lag nummer $j$ vann lag nummer $i$. När det står $\times$ betyder det att lag nummer $j$ vann. $?$ betyder att matchresultatet inte har angetts.

I detta fall finns det bara följande $1$ resultatlista som stämmer överens med den givna informationen:

• $1$:a plats: lag nummer $3$
• $2$:a plats: lag nummer $4$
• $3$:e plats: lag nummer $1$
• $4$:e plats: lag nummer $2$

Exempel 2 (När det finns flera resultatlistor som stämmer överens med informationen)

Antag att antalet lag är $3$, att lagen är numrerade från $1$ till $3$ och att matchresultaten ges av följande tabell.

I detta fall finns det följande $2$ resultatlistor som stämmer överens med den givna informationen:

• $1$:a plats: lag nummer $2$, $2$:a plats: lag nummer $1$, $3$:e plats: lag nummer $3$
• $1$:a plats: lag nummer $2$, $2$:a plats: lag nummer $3$, $3$:e plats: lag nummer $1$

Indata

På den $1$:a raden står antalet fotbollslag $n$. Varje lag är numrerat från $1$ till $n$.

På den $2$:a raden står antalet givna matchresultat $m$.

Från den $3$:e raden till rad $m + 2$ anges matchresultaten. Varje rad innehåller $2$ heltal $i, j$ åtskilda av ett blanksteg, vilket anger att lag nummer $i$ vann mot lag nummer $j$.

$n, m$ uppfyller $1 \le n \le 5000$, $1 \le m \le 100000$.

Bland de testdata som används vid bedömningen uppfyller $30\%$ villkoren $1 \le n \le 7$, $1 \le m \le 15$. Vidare uppfyller $60\%$ villkoren $1 \le n \le 100$, $1 \le m \le 2000$.

Utdata

Utdata består av $n + 1$ rader.

På de $n$ raderna från rad $1$ till rad $n$ ska du skriva ut en resultatlista som stämmer överens med den givna informationen. På rad $i$ ($1 \le i \le n$) ska du skriva ut numret på laget på $i$:te plats.

På rad $n + 1$ ska du skriva ut ett heltal som anger om det utöver den utskrivna resultatlistan finns någon annan resultatlista som stämmer överens med informationen: skriv ut $0$ om det inte finns någon, och skriv ut $1$ om det finns någon.

Exempel på indata och utdata

Exempelindata 1

Indata och utdata som motsvarar Exempel $1$ är följande.

4
5
1 2
3 1
3 2
3 4
4 1

Exempelutdata 1

3
4
1
2
0

Exempelindata 2

Indata som motsvarar Exempel $2$ är följande.

3
2
2 1
2 3

För dessa indata är följande $2$ utdata möjliga; det går bra att skriva ut vilketdera som helst.

Exempelutdata 2

2
1
3
1

2
3
1
1