CAPITALA

TIMP DE IMPLEMENTARE: Doua ore

Imperiul Roman a crescut foarte mult si este subrezit. In orice moment
pot izbucni rascoale in oricare din orasele sale. Roma nu mai este o
capitala sigura si Cezarul doreste sa mute capitala tarii si toate
trupele imperiale intr-un oras din care armatele sa poata strabate
imperiul cat mai repede; cu alte cuvinte, in orasul pentru care suma
distantelor la toate celelalte orase este minima.

Imperiul are N<=3000 orase numerotate de la 1 la N, iar reteaua de
drumuri are forma arborescenta, pentru ca armatele imperiale sa nu
aiba dificultati in alegerea traseului intre doua orase :) Distanta
intre oricare doua orase legate printr-un drum direct este de o zi de
mers.
--------
((((Pentru cei mici - "forma arborescenta" inseamna ca intre oricare
doua orase ale imperiului exista un drum si numai unul, care poate
trece prin zero, unul sau mai multe orase intermediare. Un exemplu de
retea arborescenta este poza de mai jos:

                      +---------+       +---------+    +----------+
                      |  Roma   |-------|  Atena  |----|Persepolis|
                     /+---------+       +---------+    +----------+
                   /                        |
                 /                          |
          +---------+                   +---------+
          |Cartagina|                   |  Efes   |
          +---------+                   +---------+

Se observa ca exista un unic drum, de exemplu, intre Efes si Atena
(direct) sau intre Cartagina si Persepolis (trecand prin Roma si
Atena). Cam asta e o retea arborescenta. Se poate demonstra ca o
retea arborescenta cu N noduri (orase) are N-1 muchii (drumuri
directe) intre orase.))))
---------

Se cere sa se determine orasul din care suma distantelor la celelalte
orase este minima, precum si care este aceasta suma, exprimata in zile
de mers.

DATELE DE INTRARE: Fisierul IMPERIU.IN contine un singur set de date
cu formatul:
N                       Numarul de orase
X1 Y1
X2 Y2
...
X(N-1) Y(N-1)           N-1 perechi de orase legate prin drum direct

DATELE DE IESIRE se vor afisa pe ecran in formatul:
C D

unde C este numarul orasului ales drept capitala, iar D este suma
distantelor de la C la celelalte orase.

EXEMPLU: Daca numerotam orasele Roma, Atena, Cartagina, Persepolis si
Efes din exemplul de mai sus respectiv cu 1, 2, 3, 4 si 5, atunci
obtinem fisierul de date:

IMPERIU.IN
5
2 5
2 1
1 3
4 2

Raspunsul in acest caz este:
2 5

Intr-adevar, distantele de la Atena (orasul 2) la celelalte orase sunt
respectiv de 1 (Roma), 1 (Efes), 1 (Persepolis) si 2 (Cartagina), in
total 5, adica minimul care se poate obtine.

COMPLEXITATE RECOMANDATA: O(N)
MEMORIE RECOMANDATA:      O(N)
TIMP DE RULARE:           O secunda pe un Cyrix P200 / 96MB RAM / Vindoze 95
TERMEN LIMITA:            22 decembrie 1998 (cam mult, dar asta e...)