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

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

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

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

ورودی

در خط اول ورودی دو طبیعی nn و mm، نشان‌دهنده‌ی تعداد مبحث‌های درس الگوریتم و تعداد روابط پیش‌نیازی بین مبحث‌ها، آمده است. در mm خط بعدی ورودی، در هر خط دو عدد طبیعی viv_i و uiu_i آمده است که نشان‌دهنده‌ی این است که مبحث ‌viv_i پیش نیاز مبحث uiu_i است. تضمین می‌شود هر رابطه پیش‌نیازی بین دو مبحث حداکثر یک بار در ورودی آمده است. تضمین می‌شود ترتیبی برای آموزش مبحث‌ها وجود دارد که در آن تمام رابطه‌های پیش‌نیازی رعایت شده باشد. 1n,m500 0001 \le n, m \le 500\ 000 1m(n2)1 \le m \le \binom{n}{2} 1vi,uin,viui1 \le v_i, u_i \le n, v_i \ne u_i

خروجی

در خط اول خروجی kk تعداد روش‌هایی که پیمان می‌تواند دو مبحث با شرایط گفته شده را انتخاب کند چاپ کنید. در kk خط بعدی خروجی در هر خط دو عدد aia_i و bib_i را چاپ کنید به طوری که مبحث aia_i پیش‌نیاز مبحث bib_i باشد و این دو مبحث یک روش دلخواه پیمان باشند. ترتیب خروجی باید به شکلی باشد که به ازای هر ii و jj که i<ji < j، ai<aja_i < a_j یا اگر ai=aja_i = a_j، bi<bjb_i < b_j.

زیرمسئله‌ها

زیرمسئله نمره محدودیت
۱ ۹ n9n \le 9
۲ ۲۱ n,m1 000n, m \le 1\ 000
۳ ۱۷ n1 000n \le 1\ 000
۴ ۵۳ بدون محدودیت اضافی

مثال

ورودی نمونه ۱

4 4
1 2
1 3
2 4
3 4
Plain text

خروجی نمونه ۱

0
Plain text

ورودی نمونه ۲

6 5
1 2
2 3
3 4
3 5
5 6
Plain text

خروجی نمونه ۲

2
1 2
2 3
Plain text

ورودی نمونه ۳

4 6
4 3
4 2
4 1
3 2
3 1
2 1
Plain text

خروجی نمونه ۳

3
2 1
3 2
4 3
Plain text

ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.