| VK Cup 2016 - Раунд 1 |
|---|
| Закончено |
Деревом называется связный неориентированный граф состоящий из n вершин и n - 1 ребра. Вершины пронумерованы от 1 до n.
У полярного медвежонка Лимака было дерево, пока его не украл злой Радевуш. Медвежонок очень расстроился, потому что он помнит о дереве только три числа n, d и h:
- Дерево состояло ровно из n вершин.
- Диаметр дерева был равен d. Другими словами, d это максимальное расстояние между какой-то парой вершин дерева.
- Также Лимак помнит, что если сделать корнем дерева вершину 1, то его высота будет равна h. Другими словами, h это максимальное расстояние от 1 до какой-то другой вершины.
Расстоянием между двумя вершинами дерева называется количество рёбер на простом пути между ними.
Помогите Лимаку найти какое-нибудь дерево, удовлетворяющее всем условиям и выведите его рёбра в произвольном порядке. Если подходящего дерева не существует, то выведите «-1».
В первой строке входных данных содержатся три целых числа n, d и h (2 ≤ n ≤ 100 000, 1 ≤ h ≤ d ≤ n - 1) — количество вершин, диаметр и высота дерева, если сделать вершину номер 1 корнем.
Если не существует ни одного дерева подходящего под описание Лимака, то выведите «-1» (без кавычек).
В противном случае выведите дерево, подходящее под описание Лимака. В n - 1 строке выведите пары вершин, соединённых рёбрами. Если подходящих деревьев несколько, разрешается вывести любое из них. Рёбра можно выводить в произвольном порядке.
5 3 2
1 2
1 3
3 4
3 5
8 5 2
-1
8 4 2
4 8
5 7
2 3
8 1
2 1
5 6
1 5
Ниже приведены рисунки для первого и третьего примеров.
