المپدیا

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

ابزار کاربر

ابزار سایت


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

DAG

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

ورودی

  • در سطر اول دو عدد ‎$1 \leq n \leq 100$‎ و ‎$1 \leq m \leq \frac{n \times (n-1)}{2}$‎ نمایانگر تعداد رئوس و تعداد یال‌های گراف آمده است.
  • در ‎$m$‎ سطر بعد در هر سطر یک جفت عدد ‎$a_i$‎ و ‎$b_i$‎ آمده است که نشانگر یک یال جهت‌دار از راس ‎$a_i$‎ به راس ‎$b_i$‎ است. گراف داده شده دور ندارد و هیچ دو یال داده شده یکسان نیستند.

خروجی

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

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
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

ابزار صفحه