Финал «Russian Code Cup» 2214 года будет проводиться в n гостиницах. При этом в двух гостиницах, назовем их главными, будут проводиться всевозможные мероприятия, а в остальных поселят участников. Сеть дорог устроена таким образом, что гостиницы соединены n - 1 дорогой, при этом из любой гостиницы можно попасть в любую.
Организаторам интересно, за какое минимальное количество времени все участники доберутся до главных гостиниц, если каждый участник едет в ближайшую к нему главную гостиницу, а перемещение между двумя гостиницами, соединенными дорогой, занимает одну единицу времени.
Сейчас организаторы еще окончательно не определились, какие гостиницы должны быть главными, поэтому они рассматривают различные варианты расположения главных гостиниц. Для каждого рассматриваемого расположения помогите организаторам посчитать минимальное время.
Выходные данные
На каждый запрос организаторов выведите одно целое число — время, которое понадобится, чтобы все участники добрались до главных гостиниц.