คุณเป็นนักข่าวของสำนักพิมพ์ 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