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