D. Настя и машина времени
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

Денис находится в вершине $$$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)}$$$ будет минимально возможным.

Входные данные

В первой строке находится единственное целое число $$$n$$$ $$$(1 \leq n \leq 10^5)$$$  — количество площадей в городе.

В следующих $$$n - 1$$$ строках находится по два целых числа $$$u$$$ и $$$v$$$ $$$(1 \leq v, u \leq n, u \neq v)$$$  — номера площадей, соединенных дорогой.

Гарантируется, что заданный граф является деревом.

Выходные данные

В первой строке выведите целое число $$$k$$$ $$$(1 \leq k \leq 10^6)$$$  — длина пути Дениса.

В следующих $$$k$$$ строках выведите пары $$$v_i, t_i$$$  — пары, описывающие маршрут Дениса (как в условии).

Все требования к маршруту, описанные в условии должны быть выполнены.

Гарантируется, что при заданных ограничениях существует хотя бы один маршрут и ответ, длина которого не превосходит $$$10^6$$$. Если возможных ответов несколько, выведите любой.

Пример
Входные данные
5
1 2
2 3
2 4
4 5
Выходные данные
13
1 0
2 1
3 2
3 1
2 2
4 3
4 1
5 2
5 1
4 2
2 3
2 0
1 1