Y-Path

یک گراف ساده بدون‌جهت به شما داده شده است. شما باید بزرگ‌ترین ‎$\frac{x}{y}$‎ را پیدا کنید که ‎$y$‎ راس در گراف وجود داشته باشد که بین آنها ‎$x$‎ یال وجود دارد. ‎ برای حل این سوال راه‌حل چندجمله‌ای بر حسب ‎$n$‎ وجود دارد که پاسخ هر تست را در کم‌تر از ‎$2s$‎ به دست می‌آورد.

• در سطر اول ورودی ‎$1 \leqslant n \leqslant 100$‎ و ‎$0 \leqslant m \leqslant min(1000,\frac{n \times (n-1)}{2})$‎ آمده است.
• در ‎$m$‎ سطر بعدی، در هر سطر یک جفت عدد ‎$a_i$‎ و ‎$b_i$‎ آمده است که نشان می‌دهد در گراف یک یال میان رئوس ‎$a_i$‎ و ‎$b_i$‎ قرار دارد.‎
• بین هر دو راس گراف حداکثر یک یال وجود دارد و هیچ راسی، یال به خودی ندارد.

فرض کنید ‎$a$‎ و ‎$b$‎ دو عدد هستند که ‎$a$‎ نسبت به ‎$b$‎ اول است و ‎$\frac{a}{b}=\frac{x}{y}$‎. شما باید در خروجی عبارت $a/b$ را چاپ نمایید.

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

• سوال بعد
• سوال قبل

‎ ‎