Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:آزمون های اینترنتی ۸۹ تا ۹۱:سوال ۱۵

DAG

یک DAG (گراف جهت‌دار بدون دور) به شما داده شده است ، شما باید کم‌ترین ‎k‎ای را بیابید که می‌توان ‎k‎ مسیر از گراف را طوری انتخاب کرد به طوری که هر یال در حداقل یک مسیر وجود دارد.

ورودی

  • در سطر اول دو عدد ‎1n100‎ و ‎1mn×(n1)2‎ نمایانگر تعداد رئوس و تعداد یال‌های گراف آمده است.
  • در ‎m‎ سطر بعد در هر سطر یک جفت عدد ‎ai‎ و ‎bi‎ آمده است که نشانگر یک یال جهت‌دار از راس ‎ai‎ به راس ‎bi‎ است. گراف داده شده دور ندارد و هیچ دو یال داده شده یکسان نیستند.

خروجی

در تنها سطر خروجی جواب سوال را چاپ کنید. ‎

محدودیت‌ها

  • محدودیت زمان: ۱۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
2 1
1 2
1
3 2
1 2
2 3
1
6 7‎
1 2‎
2 3‎
1 3‎
3 4‎
4 5‎
5 6‎
‎4 6
2

ابزار صفحه