Yong-In pilsēta plāno izveidot autobusu maršrutu tīklu ar N pieturām. Katra pietura atrodas uz ielu stūra. Yong-In ir moderna pilsēta, tāpēc tās karte izskatās kā režģis, kas veidots no vienādiem kvadrātveida blokiem. Paredzēts, ka divas autobusu pieturas tiks izvēlētas par mezglu pieturām H₁ un H₂. Šīs mezglu pieturas tiks savienotas savā starpā ar tiešu autobusa maršrutu un katra no atlikušajām N-2 pieturām tiks tieši savienota vai nu ar H₁ , vai H₂ (bet ne ar abām), un ne ar vienu citu autobusa pieturu.

Attālums starp jebkurām divām autobusu pieturām ir vienāds ar īsākā iespējamā maršruta, kas iet pa ielām, garumu. Tas ir, ja pieturu apzīmēšanai lieto koordinātas (x, y), tad attālums starp divām pieturām (x₁, y₁) un (x₂, y₂), no kurām vismaz viena ir mezgla pietura, ir . Ja divas autobusu pieturas A un B ir savienotas ar vienu un to pašu mezgla pieturu H₁, tad maršruta no A uz B garums ir vienāds ar divu attālumu (no A līdz H₁ un no H₁ līdz B) summu. Ja pieturas A un B ir savienotas ar dažādām mezgla pieturām, piem., A ar H₁ un B ar H₂, tad maršruta no A uz B garums ir trīs attālumu (no A līdz H₁, no H₁ līdz H₂, un no H₂ līdz B) summa.

Yong-In pilsētas plānošanas speciālisti vēlas, lai pilsētnieki katru punktu pilsētā sasniegtu pēc iespējas ātrāk. Tāpēc viņi gribētu mezgla pieturas izvēlēties tā, lai iegūtajā maršrutu tīklā garākais maršruts starp jebkurām divām pieturām būtu īsākais iespējamais. Viena mezgla pieturu izvēle un pārējo pieturu piesaiste tām P ir labāka par citu izvēli Q , ja garākā maršruta garums izvēlē P ir īsāks kā izvēlē Q.

Jūsu uzdevums ir uzrakstīt programmu, kas aprēķina garākā maršruta garumu vislabākajai izvēlei. 

Ievaddatu pirmā rinda satur naturālu skaitli N, 2 <= N <= 500, kas apzīmē pieturu skaitu. Katrā no nākošajām N faila rindām tiek dotas kādas pieturas x un y koordinātas. Koordinātu vērtības ir naturāli skaitļi, 0<x,y <= 5000. Nekādas divas autobusu pieturas neatrodas vienā un tajā pašā vietā.

Izvaddatu vienīgajā rindā jāizvada viens naturāls skaitlis - īsākais iespējamais garākā autobusa maršruta garums.

 
Uzdevums izmantots Vispasaules 14.informātikas olimpiādē Yong-In (Koreja) 2002.gadā.