Autobusy

Limit pamięci: 32 MB

Prezydent Bajtogrodu planuje budowę sieci komunikacyjnej, składającej się z przystanków i linii autobusowych. Dwa spośród przystanków, i zostaną wybrane na węzły przesiadkowe, a pozostałe przystanków zostanie połączonych bezpośrednimi liniami autobusowymi z albo (ale nie z obydwoma jednocześnie). Ponadto, w mieście zostanie utworzona linia autobusowa łącząca obydwa węzły przesiadkowe. Z powodu braku funduszy, nie powstaną żadne inne połączenia autobusowe.

Odległość pomiędzy przystankami autobusowymi połączonymi bezpośrednią linią autobusową, znajdującymi się w punktach o współrzędnych i wynosi . Jeżli dwa przystanki połączone są bezpośrednio z tym samym węzłem, to odległość między nimi jest sumą odległości obydwóch przystanków od tego węzła. Jeśli dwa przystanki połączone są z różnymi węzłami przesiadkowymi, to odległość między nimi jest sumą odległości każdego z przystanków od węzła do którego jest on podłączony i odległości pomiędzy węzłami przesiadkowymi.

Zadanie

Napisz program, który:

• wczyta rozmieszczenie przystanków autobusowych ze standardowego wejścia,
• wyznaczy przystanki, które należy wybrać jako węzły przesiadkowe oraz pary przystanków, które należy połączyć bezpośrednimi liniami autobusowymi, tak aby maksymalna odległość pomiędzy dowolnymi dwoma przystankami była jak najmniejsza,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszej lini standardowego wejścia znajudje się jedna liczba całkowita (), oznaczająca liczbę wszystkich przystanków w mieście. Każda z kolejnych linii zawiera dwie liczby całkowite dodatnie, nie większe niż - są to współrzędne jednego z przystanków autobusowych. W danym punkcie może znajdować się co najwyżej jeden przystanek.

Wyjście

Twój program powinien zapisać w pierwszym i jedynym wierszu standardowego wyjścia wypisać jedną liczbę całkowitą - największą odległość pomiędzy dwoma przystankami autobusowymi w mieście, przy optymalnym doborze węzłów przesiadkowych i połączeniu przystanków z węzłami.

Przykład

Dla danych wejściowych:

6
1 7
16 6
12 4
4 4
1 1
11 1

poprawną odpowiedzią jest:

20

Przykładowym danym wejściowym odpowiada powyższy schemat. Przystanki numer 3 i 4 zostały wybrane na węzły przesiadkowe.

Zapożyczone ze starego IOI przez Jakuba Łąckiego.