Деревом называется связный неориентированный граф состоящий из n вершин и n - 1 ребра. Вершины пронумерованы от 1 до n.
У полярного медвежонка Лимака было дерево, пока его не украл злой Радевуш. Медвежонок очень расстроился, потому что он помнит о дереве только три числа n, d и h:
Расстоянием между двумя вершинами дерева называется количество рёбер на простом пути между ними.
Помогите Лимаку найти какое-нибудь дерево, удовлетворяющее всем условиям и выведите его рёбра в произвольном порядке. Если подходящего дерева не существует, то выведите «-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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач