Придя к Насте, Денис обнаружил, что она ему не рада... Но у молодого человека есть последняя надежда. Он хочет купить все вещи, что нравятся Насте. Тогда-то она уж точно согласится с ним общаться.

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

Денис находится в вершине $$$1$$$ в момент времени $$$0$$$. Он хочет хоть раз побывать в каждой вершине и вернуться назад как можно раньше.

Денис может проходить вдоль любой дороги за $$$1$$$ времени. Увы, город столь велик, что сделать это быстро никак не выйдет. Поэтому Денис пошел на отчаянный шаг. Он достал свою карманную машину времени, которую он собрал у себя в подвале. С ее помощью Денис может стоя на месте сменить время на любое неотрицательное время, которое меньше текущего.

Но у машины времени есть один нюанс. Если герой окажется в одном месте и в одно и то же время дважды, произойдет взрыв вселенских масштабов и не получится порадовать Настю. Поэтому Денис просит вас проложить ему маршрут с использованием машины времени такой, что он обойдет все площади и вернется на первую и при этом максимальное время в котором он побывал будет минимально.

Формально, маршрут Дениса можно представить как последовательность пар $$$\{v_1, t_1\}, \{v_2, t_2\}, \{v_3, t_3\}, \ldots, \{v_k, t_k\}$$$, где $$$v_i$$$ — номер площади, а $$$t_i$$$  — время, в котором сейчас находится мальчик.

Должны быть выполнены следующие условия:

• Маршрут начинается на площади $$$1$$$ в момент времени $$$0$$$, то есть $$$v_1 = 1, t_1 = 0$$$ и заканчивается на площади $$$1$$$, то есть $$$v_k = 1$$$.
• Все переходы делятся на два типа:
  1. Стоя на площади сменить время: $$$\{ v_i, t_i \} \to \{ v_{i+1}, t_{i+1} \} : v_{i+1} = v_i, 0 \leq t_{i+1} < t_i$$$.
  2. Пройти по одной из дорог: $$$\{ v_i, t_i \} \to \{ v_{i+1}, t_{i+1} \}$$$. При этом $$$v_i$$$ и $$$v_{i+1}$$$ соединены дорогой и $$$t_{i+1} = t_i + 1$$$.
• Все пары $$$\{ v_i, t_i \}$$$ должны быть различны.
• Среди $$$v_1, v_2, \ldots, v_k$$$ встречаются все площади.

Вам нужно найти маршрут такой, что максимальное время, в котором побывает Денис будет минимальным, то есть маршрут, для которого $$$\max{(t_1, t_2, \ldots, t_k)}$$$ будет минимально возможным.