• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• منبع: آزمون نهایی سوم دوره ۲۶ المپیاد کامپیوتر

---

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

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

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

ورودی

در خط اول ورودی دو طبیعی $n$ و $m$، نشان‌دهنده‌ی تعداد مبحث‌های درس الگوریتم و تعداد روابط پیش‌نیازی بین مبحث‌ها، آمده است. در $m$ خط بعدی ورودی، در هر خط دو عدد طبیعی $v_i$ و $u_i$ آمده است که نشان‌دهنده‌ی این است که مبحث ‌$v_i$ پیش نیاز مبحث $u_i$ است. تضمین می‌شود هر رابطه پیش‌نیازی بین دو مبحث حداکثر یک بار در ورودی آمده است. تضمین می‌شود ترتیبی برای آموزش مبحث‌ها وجود دارد که در آن تمام رابطه‌های پیش‌نیازی رعایت شده باشد. $$1 \le n, m \le 500\ 000$$ $$1 \le m \le \binom{n}{2}$$ $$1 \le v_i, u_i \le n, v_i \ne 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 1\ 000$
۳	۱۷	$n \le 1\ 000$
۴	۵۳	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

4 4
1 2
1 3
2 4
3 4

خروجی نمونه ۱

0

ورودی نمونه ۲

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

خروجی نمونه ۲

2
1 2
2 3

ورودی نمونه ۳

4 6
4 3
4 2
4 1
3 2
3 1
2 1

خروجی نمونه ۳

3
2 1
3 2
4 3