پیمان به علی قول داده است که در آموزش درس الگوریتم دوره تابستان به او کمک خواهد کمک کرد. مشکل اینجاست که او در مشهد زندگی می‌کند و دوست ندارد مدت زیادی از خانه‌اش دور باشد. به همین دلیل علی از او خواسته تنها دو مبحث از $n$ مبحث درس الگوریتم را آموزش بدهد.

درس الگوریتم $n$ مبحث دارد که هر کدام از مبحث‌ها ممکن است پیش‌نیاز تعدادی از مبحث‌های دیگر باشند. ترتیب آموزش مبحث‌ها در دوره‌ی تابستان مشخص نیست ولی می‌دانیم که روابط پیش‌نیازی در این ترتیب رعایت خواهند شد. (اگر مبحثی پیش‌نیاز یک مبحث دیگر باشد قطعاً زودتر آموزش داده می‌شود) هم‌چنین می‌دانیم که آموزش یک مبحث دقیقاٌ یک روز طول می‌کشد و طبق برنامه قرار است در طی $n$ روز تمامی مبحث‌های درس الگوریتم آموزش داده شود.

پیمان در نظر دارد که در طی یک سفر دو روزه به تهران به قول خود عمل کند، دو مبحث در درس الگوریتم آموزش دهد، و به خانه برگردد. به همین خاطر او باید دو مبحث را به نحوی انتخاب کند که در هر ترتیبی از مبحث‌ها که برای آموزش الگوریتم انتخاب می‌شود، آن دو مبحث در دو روز متوالی در برنامه بیایند. هم‌چنین پیمان دوست ندارد مبحث‌هایی که آموزش می‌دهد نامرتبط باشند و می‌خواهد به شکلی آن دو مبحث را انتخاب کند که یکی از آن‌ها پیش‌نیاز دیگری باشد. او به چه روش‌هایی می‌تواند دو مبحث را با شرایط دلخواه‌ش انتخاب کند؟

در خط اول ورودی دو طبیعی $n$ و $m$، نشان‌دهنده‌ی تعداد مبحث‌های درس الگوریتم و تعداد روابط پیش‌نیازی بین مبحث‌ها، آمده است.

در $m$ خط بعدی ورودی، در هر خط دو عدد طبیعی $v_i$ و $u_i$ آمده است که نشان‌دهنده‌ی این است که مبحث ‌$v_i$ پیش نیاز مبحث $u_i$ است.

در خط اول خروجی $k$ تعداد روش‌هایی که پیمان می‌تواند دو مبحث با شرایط گفته شده را انتخاب کند چاپ کنید.

در $k$ خط بعدی خروجی در هر خط دو عدد $a_i$ و $b_i$ را چاپ کنید به طوری که مبحث $a_i$ پیش‌نیاز مبحث $b_i$ باشد و این دو مبحث یک روش دلخواه پیمان باشند. ترتیب خروجی باید به شکلی باشد که به ازای هر $i$ و $j$ که $i < j$، $a_i < a_j$ یا اگر $a_i = a_j$، $b_i < b_j$.

• زیرمسئله اول (۹ نمره): $n \le 9$
• زیرمسئله دوم (۲۱ نمره): $n, m \le 1000$
• زیرمسئله سوم (۱۷ نمره):$n \le 1000$
• زیرمسئله چهارم(۵۳ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $1 \le n, m \le 5 \times 10^5$
• $1 \le m \le \binom{n}{2}$
• $1 \le v_i, u_i \le n, v_i \ne u_i$
• تضمین می‌شود هر رابطه پیش‌نیازی بین دو مبحث حداکثر یک بار در ورودی آمده است.
• تضمین می‌شود ترتیبی برای آموزش مبحث‌ها وجود دارد که در آن تمام رابطه‌های پیش‌نیازی رعایت شده باشد.

• سوال قبل