capitala

Capitala

== include(page="template/taskheader" task_id="capitala") ==

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 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.

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$ 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.

h2. Date de intrare

h2. Restrictii

* $1 ≤ N ≤ 100 000$

* $1 ≤ N ≤ 200 000$
* Daca sunt mai multe posibilitati de a aseza capitala, afisati oricare dintre acestea
* Nu se vor acorda punctaje partiale

h2. Exemplu

1 3
4 2| 2 5 |

h3. Explicatie
 
...
 

== include(page="template/taskfooter" task_id="capitala") ==

2193