أنت مراسل في صحيفة 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