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

Нам было очень сложно придумать тесты для задачи D. Чтобы подготовить сильные тесты, нам пришлось решить следующую задачу.

Для заданного неориентированного помеченного дерева, состоящего из $$$n$$$ вершин, найдите набор отрезков, такой что:

  1. концы каждого отрезка являются целыми числами от $$$1$$$ до $$$2n$$$, и каждое целое число от $$$1$$$ до $$$2n$$$ должно встречаться как конец ровно одного отрезка;
  2. все отрезки — невырожденные;
  3. для каждой такой пары чисел $$$(i, j)$$$, что $$$i \ne j$$$, $$$i \in [1, n]$$$ и $$$j \in [1, n]$$$, вершины $$$i$$$ и $$$j$$$ соединены ребром тогда и только тогда, когда отрезки $$$i$$$ и $$$j$$$ пересекаются, но ни отрезок $$$i$$$ не содержится полностью в отрезке $$$j$$$, ни отрезок $$$j$$$ полностью не содержится в отрезке $$$i$$$.

А вы можете решить эту задачу?

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — количество вершин в дереве.

Следующие $$$n - 1$$$ строк содержат по два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \ne y_i$$$), описывающие концы $$$i$$$-го ребра.

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

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

Выведите $$$n$$$ пар целых чисел, $$$i$$$-я пара должна содержать два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i < r_i \le 2n$$$) — концы $$$i$$$-го отрезка. Все $$$2n$$$ целых чисел, которые вы вывели, должны быть различными.

Гарантируется, что ответ всегда существует.

Примеры
Входные данные
6
1 2
1 3
3 4
3 5
2 6
Выходные данные
9 12
7 10
3 11
1 5
2 4
6 8
Входные данные
1
Выходные данные
1 2