Нам было очень сложно придумать тесты для задачи D. Чтобы подготовить сильные тесты, нам пришлось решить следующую задачу.
Для заданного неориентированного помеченного дерева, состоящего из \(n\) вершин, найдите набор отрезков, такой что:
А вы можете решить эту задачу?
Первая строка содержит одно целое число \(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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач