← 返回题目列表

Codeforces · 639/B

B. 熊与被遗忘的树 3

中文机器翻译题面 查看原题

树是由 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

注意

下面您可以看到第一个示例和第三个示例中打印到输出的树。