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