树是由 n 个顶点和 n - 1 条边组成的连通无向图。顶点编号为 1 到 n。
Limak 是一只小北极熊,Radewoosh 是他的邪恶敌人。利马克曾经有一棵树,但拉德伍什偷走了它。小熊现在非常难过,因为他对这棵树不太记得了——他只能告诉你三个值 n、d 和 h:
- 树正好有 n 个顶点。
- 树的直径为 d。换句话说,d 是两个顶点之间的最大距离。
- Limak 还记得他曾经将树植根于顶点 1,之后它的高度为 h。换句话说,h 是顶点 1 与其他顶点之间的最大距离。
树的两个顶点之间的距离是它们之间的简单路径上的边数。
帮助利马克恢复他的树。检查是否存在满足给定条件的树。找到任何这样的树并以任意顺序打印其边缘。也有可能 Limak 犯了一个错误,并且没有合适的树 - 在这种情况下打印“-1”。
输入
第一行包含三个整数 n、d 和 h (2 ≤ n ≤ 100 000, 1 ≤ h ≤ d ≤ n - 1)——分别是在顶点 1 求根后的顶点数量、直径和高度。
输出
如果没有与 Limak 记住的树匹配的树,则打印唯一带有“-1”的行(不带引号)。
否则,描述与 Limak 的描述相匹配的任何树。打印 n - 1 行,每行有两个空格分隔的整数——由边连接的顶点的索引。如果有很多有效树,则打印其中任何一个。您可以按任何顺序打印边缘。
示例
输入 #1
5 3 2
输出 #1
1 2 1 3 3 4 3 5
输入 #2
8 5 2
输出 #2
-1
输入 #3
8 4 2
输出 #3
4 8 5 7 2 3 8 1 2 1 5 6 1 5
注意
下面您可以看到第一个示例和第三个示例中打印到输出的树。