Царь Пантелеймон сильно заводом по производству упаковки заинтересовался. Подробно выспрашивал Калистрата о нём, а потом пожелал увидеть строящиеся цеха. Так что пришлось министру экономики сказать, что нет пока завода — место под него хорошее выбрать надобно. Ведь завод будет всё царство упаковкой снабжать, потому среди всех возможных вариантов размещения надо выбрать тот, в котором расстояние от города, где будет построен завод, до самого отдалённого города царства будет минимальным.

В царстве n городов, и некоторые пары этих городов связаны двусторонними дорогами. Точно известно, что из любого города царства можно доехать до любого другого города.

Ваша задача — определить, в каком городе следует построить завод.