E. Построение дерева
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задано три целых числа $$$n$$$, $$$d$$$ и $$$k$$$.

Ваша задача состоит в том, чтобы построить неориентированное дерево, состоящее из $$$n$$$ вершин, имеющее диаметр $$$d$$$ и степень каждой вершины не более $$$k$$$, или сказать, что это невозможно.

Неориентированное дерево — это связный неориентированный граф с $$$n - 1$$$ ребром.

Диаметр дерева — это максимальная длина простого пути (пути, в котором каждая вершина встречается не более одного раза) между всеми парами вершин этого дерева.

Степень вершины — это количество ребер, инцидентных этой вершине (то есть для вершины $$$u$$$ это количество ребер $$$(u, v)$$$, принадлежащих дереву, где $$$v$$$ это любая другая вершина дерева).

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

Первая строка входных данных содержит три целых числа $$$n$$$, $$$d$$$ и $$$k$$$ ($$$1 \le n, d, k \le 4 \cdot 10^5$$$).

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

Если не существует дерева, удовлетворяющего описанным выше ограничениям, выведите одно слово «NO» (без кавычек).

Иначе в первой строке выведите «YES» (без кавычек) и затем $$$n - 1$$$ строку, которые описывают ребра дерева, удовлетворяющего описанным выше ограничениям. Вершины дерева должны быть пронумерованы от $$$1$$$ до $$$n$$$. Вы можете выводить ребра дерева и пары вершин ребра в любом порядке. Если существует несколько ответов, выведите любой из них.

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