Придя к Насте, Денис обнаружил, что она ему не рада... Но у молодого человека есть последняя надежда. Он хочет купить все вещи, что нравятся Насте. Тогда-то она уж точно согласится с ним общаться.
Карта города, в котором живут наши герои, представляет собой множество площадей, некоторые из которых соединены дорогами. От любой площади можно добраться до любой другой ровно одним способом, используя эти дороги и не посещая одну и ту же площадь дважды. Получается, что граф города — это дерево.
Денис находится в вершине \(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\).
- Все переходы делятся на два типа:
- Стоя на площади сменить время: \(\{ v_i, t_i \} \to \{ v_{i+1}, t_{i+1} \} : v_{i+1} = v_i, 0 \leq t_{i+1} < t_i\).
- Пройти по одной из дорог: \(\{ 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)}\) будет минимально возможным.
Выходные данные
В первой строке выведите целое число \(k\) \((1 \leq k \leq 10^6)\) — длина пути Дениса.
В следующих \(k\) строках выведите пары \(v_i, t_i\) — пары, описывающие маршрут Дениса (как в условии).
Все требования к маршруту, описанные в условии должны быть выполнены.
Гарантируется, что при заданных ограничениях существует хотя бы один маршрут и ответ, длина которого не превосходит \(10^6\). Если возможных ответов несколько, выведите любой.