问题 AO: Limak and Forgotten Tree 3
内存限制:136 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:27
解决:14
题目描述
树是由n个顶点和n个顶点组成的连通无向图,将顶点从1到n进行编号。
Redwoosh是Limak的邪恶敌人。Limak曾经有一棵树,但Redwoosh偷走了它。Limak现在很伤心,因为他对这棵树不太记得了,他只能告诉你三个值n、d和h:
(1)这棵树正好有n个顶点。
(2)树的直径为d。即d是两个顶点之间的最大距离。
(3)Limak还记得,他曾经将树植于顶点1,之后树的高度是h。即h是顶点1和某些其他顶点之间的最大距离。
(4)树的两个顶点之间的距离是它们之间的简单路径上的边数。
帮助Limak修复他的树。检查是否存在满足给定条件的树。找到任何这样的树,并以任何顺序打印其边缘。也可能是Limak犯了一个错误,并没有合适的树,在这种情况下,打印“-1”。
Redwoosh是Limak的邪恶敌人。Limak曾经有一棵树,但Redwoosh偷走了它。Limak现在很伤心,因为他对这棵树不太记得了,他只能告诉你三个值n、d和h:
(1)这棵树正好有n个顶点。
(2)树的直径为d。即d是两个顶点之间的最大距离。
(3)Limak还记得,他曾经将树植于顶点1,之后树的高度是h。即h是顶点1和某些其他顶点之间的最大距离。
(4)树的两个顶点之间的距离是它们之间的简单路径上的边数。
帮助Limak修复他的树。检查是否存在满足给定条件的树。找到任何这样的树,并以任何顺序打印其边缘。也可能是Limak犯了一个错误,并没有合适的树,在这种情况下,打印“-1”。
输入
第一行包含三个整数n、d和h(2≤n≤100000,1≤h≤d≤n-1),分别是生于顶点1之后后的顶点数、直径和高度。
输出
如果没有与Limak记住的树匹配的树,那么只打印一行“-1”(不带引号)。
否则,请描述与Limak描述匹配的任何的树。打印n - 1行,每行有两个以空格分隔的整数——由边连接的顶点的索引。如果有许多有效的树,请打印其中任何的一棵。可以按任何顺序打印边缘。
否则,请描述与Limak描述匹配的任何的树。打印n - 1行,每行有两个以空格分隔的整数——由边连接的顶点的索引。如果有许多有效的树,请打印其中任何的一棵。可以按任何顺序打印边缘。
样例输入 复制
5 3 2
样例输出 复制
1 2
1 3
3 4
3 5
提示
Below you can see trees printed to the output in the first sample and the third sample.