DAG
یک DAG (گراف جهتدار بدون دور) به شما داده شده است ، شما باید کمترین kای را بیابید که میتوان k مسیر از گراف را طوری انتخاب کرد به طوری که هر یال در حداقل یک مسیر وجود دارد.
ورودی
در سطر اول دو عدد 1≤n≤100 و 1≤m≤n×(n−1)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 |