אתם כתבים של עיתון JOI ואחראים על כתבות הספורט.
עד אתמול נערך בקרואטיה טורניר ליגה בשיטת ליגה שבה כל קבוצה משחקת נגד כל שאר הקבוצות בהשתתפות $n$ קבוצות כדורגל. נראה כי הוועדה המארגנת של הטורניר קבעה לכל קבוצה דירוג מהמקום ה-$1$ ועד המקום ה-$n$ בהתבסס על תוצאות המשחקים והתקנון. יחד עם תוצאות הניצחון וההפסד של חלק מהמשחקים, נמסר לכם המידע הבא:
- מידע $1$: לא היו משחקים שהסתיימו בתיקו.
- מידע $2$: לכל הקבוצות נקבעו דירוגים שונים.
- מידע $3$: לכל $1 \le a < b \le n$, במשחק בין הקבוצה שבמקום ה-$a$ לבין הקבוצה שבמקום ה-$b$, תמיד ניצחה הקבוצה שבמקום ה-$a$.
כדי להכין את הכתבה, החלטתם לשער את טבלת הדירוג על סמך תוצאות חלק מהמשחקים ופרטי המידע $1$–$3$ שנמסרו לכם.
כתבו תוכנית המקבלת כקלט את תוצאות הניצחון וההפסד של חלק מהמשחקים, ומדפיסה טבלת דירוג $1$ המתאימה למידע שנמסר. כמו כן, קבעו האם קיימת טבלת דירוג נוספת המתאימה למידע שנמסר מלבד טבלת הדירוג שהודפסה.
כאן, טבלת דירוג פירושה רשימת הקבוצות המסודרת לפי הסדר מהמקום ה-$1$ ועד המקום ה-$n$.
דוגמאות
דוגמה 1 (מקרה שבו קיימת רק טבלת דירוג $1$ המתאימה למידע)
נניח שמספר הקבוצות הוא $4$, הקבוצות ממוספרות מ-$1$ עד $4$, ותוצאות המשחקים נתונות בטבלה הבאה.
| $i \backslash j$ | $1$ | $2$ | $3$ | $4$ |
|---|---|---|---|---|
| $1$ | $-$ | $\circ$ | $\times$ | $\times$ |
| $2$ | $\times$ | $-$ | $\times$ | $?$ |
| $3$ | $\circ$ | $\circ$ | $-$ | $\circ$ |
| $4$ | $\circ$ | $?$ | $\times$ | $-$ |
כאשר בשורה $i$ ובעמודה $j$ מופיע $\circ$, פירוש הדבר שבמשחק בין קבוצה מספר $i$ לבין קבוצה מספר $j$, קבוצה מספר $i$ ניצחה. כאשר מופיע $\times$, פירוש הדבר שקבוצה מספר $j$ ניצחה. $?$ פירושו שתוצאת המשחק אינה נתונה.
במקרה זה, ישנה רק טבלת דירוג $1$ המתאימה למידע שנמסר, והיא:
- מקום $1$: קבוצה מספר $3$
- מקום $2$: קבוצה מספר $4$
- מקום $3$: קבוצה מספר $1$
- מקום $4$: קבוצה מספר $2$
דוגמה 2 (מקרה שבו קיימות מספר טבלאות דירוג המתאימות למידע)
נניח שמספר הקבוצות הוא $3$, הקבוצות ממוספרות מ-$1$ עד $3$, ותוצאות המשחקים נתונות בטבלה הבאה.
| $i \backslash j$ | $1$ | $2$ | $3$ |
|---|---|---|---|
| $1$ | $-$ | $\times$ | $?$ |
| $2$ | $\circ$ | $-$ | $\circ$ |
| $3$ | $?$ | $\times$ | $-$ |
במקרה זה, ישנן $2$ טבלאות דירוג המתאימות למידע שנמסר, והן:
- מקום $1$: קבוצה מספר $2$, מקום $2$: קבוצה מספר $1$, מקום $3$: קבוצה מספר $3$
- מקום $1$: קבוצה מספר $2$, מקום $2$: קבוצה מספר $3$, מקום $3$: קבוצה מספר $1$
קלט
בשורה ה-$1$ רשום מספר קבוצות הכדורגל $n$. לכל קבוצה מוצמד מספר מ-$1$ עד $n$.
בשורה ה-$2$ רשום מספר תוצאות המשחקים הנתונות $m$.
מהשורה ה-$3$ ועד השורה ה-$m + 2$ מופיעות תוצאות המשחקים. כל שורה מכילה $2$ מספרים שלמים $i, j$ המופרדים ברווח, ומציינת שקבוצה מספר $i$ ניצחה את קבוצה מספר $j$.
$n, m$ מקיימים $1 \le n \le 5000$, $1 \le m \le 100000$.
מתוך נתוני הבדיקה המשמשים לניקוד, $30\%$ מקיימים $1 \le n \le 7$, $1 \le m \le 15$. בנוסף, $60\%$ מקיימים $1 \le n \le 100$, $1 \le m \le 2000$.
פלט
הפלט מורכב מ-$n + 1$ שורות.
ב-$n$ השורות מהשורה ה-$1$ ועד השורה ה-$n$, פלטו טבלת דירוג המתאימה למידע שנמסר. בשורה ה-$i$ ($1 \le i \le n$) פלטו את מספרה של הקבוצה שבמקום ה-$i$.
בשורה ה-$n + 1$, פלטו מספר שלם המציין האם קיימת טבלת דירוג נוספת המתאימה למידע שנמסר מלבד טבלת הדירוג שהודפסה: אם לא קיימת פלטו $0$, ואם קיימת פלטו $1$.
דוגמאות קלט ופלט
קלט לדוגמה 1
הקלט והפלט המתאימים לדוגמה $1$ הם כדלקמן.
4 5 1 2 3 1 3 2 3 4 4 1
פלט לדוגמה 1
3 4 1 2 0
קלט לדוגמה 2
נתוני הקלט המתאימים לדוגמה $2$ הם כדלקמן.
3 2 2 1 2 3
עבור נתוני קלט אלו, אפשריים $2$ נתוני הפלט הבאים; ניתן לפלוט כל אחד מהם.
פלט לדוגמה 2
2 1 3 1
2 3 1 1