bus Autobusu pieturas 4 sek.  Uzdevums 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 H1 un H2. Šī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 H1 , vai H2 (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 (x1, y1) un (x2, y2), 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 H1, tad maršruta no A uz B garums ir vienāds ar divu attālumu (no A līdz H1 un no H1 līdz B) summu. Ja pieturas A un B ir savienotas ar dažādām mezgla pieturām, piem., A ar H1 un B ar H2, tad maršruta no A uz B garums ir trīs attālumu (no A līdz H1, no H1 līdz H2, un no H2 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.    Ievaddati Teksta faila bus.in 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ā.    Izvaddati Teksta faila bus.out vienīgajā rindā jāizvada viens naturāls skaitlis - īsākais iespējamais garākā autobusa maršruta garums.    Piemērs bus.in bus.out 7 7 9 10 9 5 3 1 1 7 2 15 6 17 7 25    Atsauces Uzdevums izmantots Vispasaules 14.informātikas olimpiādē Yong-In (Koreja) 2002.gadā. Drukāšanai