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$ را چاپ نمایید.

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