یک مسیر $n$ راسی در یک گراف دنباله‌ای به طول $n$ از رئوس است. یک مسیر فضایی $n$ راسی دنباله‌ای از نقاط است که در یک صفحه آمده اند و به صورت یک مسیر به ترتیب به هم وصل هستند. فاصله دو راس مجاور $i$ و $i+1$ برابر طول یال آن‌ها می‌باشد ( طول یال در فضا برابر مقدار فاصله دو نقطه در صفحه اقلیدسی می‌باشد). فاصله فضایی دو راس $i$ و $j$ مجموع طول یال‌هایی می‌باشد که راس $i$ را به راس $j$ می‌رساند ( مسیر متصل کننده این دو راس (.
هدف پیدا کردن بیش‌ترین مقدار نسبت فاصله فضایی دو راس $i$ و $j$ به فاصله اقلیدسی آن‌ها می‌باشد.
در تنها سطر فایل خروجی قسمت صحیح مقدار بیشینه نسبت فاصله فضایی و فاصله اقلیدسی را بنویسید.