Нам было очень сложно придумать тесты для задачи D. Чтобы подготовить сильные тесты, нам пришлось решить следующую задачу.
Для заданного неориентированного помеченного дерева, состоящего из \(n\) вершин, найдите набор отрезков, такой что:
- концы каждого отрезка являются целыми числами от \(1\) до \(2n\), и каждое целое число от \(1\) до \(2n\) должно встречаться как конец ровно одного отрезка;
- все отрезки — невырожденные;
- для каждой такой пары чисел \((i, j)\), что \(i \ne j\), \(i \in [1, n]\) и \(j \in [1, n]\), вершины \(i\) и \(j\) соединены ребром тогда и только тогда, когда отрезки \(i\) и \(j\) пересекаются, но ни отрезок \(i\) не содержится полностью в отрезке \(j\), ни отрезок \(j\) полностью не содержится в отрезке \(i\).
А вы можете решить эту задачу?
Выходные данные
Выведите \(n\) пар целых чисел, \(i\)-я пара должна содержать два целых числа \(l_i\) и \(r_i\) (\(1 \le l_i < r_i \le 2n\)) — концы \(i\)-го отрезка. Все \(2n\) целых чисел, которые вы вывели, должны быть различными.
Гарантируется, что ответ всегда существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 2
1 3
3 4
3 5
2 6
|
9 12
7 10
3 11
1 5
2 4
6 8
|
|
2
|
1
|
1 2
|