Codeforces 639B.Bear and Forgotten Tree 3

175


题目




Description  


A tree is a connected undirected graph consisting of n vertices and n - 1 edges. Vertices are numbered 1 through n.

Limak is a little polar bear and Radewoosh is his evil enemy. Limak once had a tree but Radewoosh stolen it. Bear is very sad now because he doesn't remember much about the tree — he can tell you only three values n, d and h:

The tree had exactly n vertices.
The tree had diameter d. In other words, d was the biggest distance between two vertices.
Limak also remembers that he once rooted the tree in vertex 1 and after that its height was h. In other words, h was the biggest distance between vertex 1 and some other vertex.
The distance between two vertices of the tree is the number of edges on the simple path between them.

Help Limak to restore his tree. Check whether there exists a tree satisfying the given conditions. Find any such tree and print its edges in any order. It's also possible that Limak made a mistake and there is no suitable tree – in this case print "-1".



Input  


The first line contains three integers n, d and h (2 ≤ n ≤ 100 000, 1 ≤ h ≤ d ≤ n - 1) — the number of vertices, diameter, and height after rooting in vertex 1, respectively.


Output  


If there is no tree matching what Limak remembers, print the only line with "-1" (without the quotes).

Otherwise, describe any tree matching Limak's description. Print n - 1 lines, each with two space-separated integers – indices of vertices connected by an edge. If there are many valid trees, print any of them. You can print edges in any order.


Sample Input  


Input  


5 3 2

>>

Output  


1 2
1 3
3 4
3 5


Input  


8 5 2


Output  


-1


Input  


8 4 2

>>

Output  


4 8
5 7
2 3
8 1
2 1
5 6
1 5


题解


这道题的解只需要输出任意一组解即可
输入的 ndh 分别是节点数、最大距离、从 1 的最大距离
由于不需要考虑解的输出问题
因此我们可以只考虑最简单的情况

例如第一组样例( 5 3 2 )
样例1图解
我们先考虑 h1 开始最远要连到 2
因此连接 1 -> 22 -> 3
又由于最远只能连接到 3 ,除去已经连接的 2 应该有 连接长度不超过 h 并且与 h 加起来不超过 d
可以继续连接 d-h 长度 1 -> 4

最后将没有连接的节点都连接到 1

分析下 需要输出 0 的情况为 h * 2 < d 即在满足从 1 出发的最远为 h 的情况下不可能最远为 d

而我们还可以额外考虑下 d == h 的情况
如果 d == 1 && h == 1 显然只有 n == 2 可能有解(画一下就能明白)

而其他情况(如 5 2 2 )
图解
可以发现,有如图的情况是合法的

考虑好这些情况即可~

代码


/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
using namespace std;

const int maxn = 150005;


bool Do() {
    int n,d,h;
    if(scanf("%d%d%d",&n,&d,&h) == EOF)
        return false;

    //printf("\n%d %d %d\n",n,d,h);

    if(h * 2 < d) {
        printf("-1\n");
        return true;
    }


    if(d == h) {
        if(d == 1 && n != 2) {
            printf("-1\n");
            return true;
        }

        int pos = 2;

        for(int i = 0;i < h;i++) {
            printf("%d %d\n",pos - 1,pos);
            pos++;
        }
        
        while(pos <= n)
            printf("2 %d\n",pos++);

    } else {
        int pos = 2;

        for(int i = 0;i < h;i++) {
            printf("%d %d\n",pos - 1,pos);
            pos++;
        }

        for(int i = 0;i < d - h;i++) {
            if(i == 0) {
                printf("1 %d\n",pos);
            } else {
                printf("%d %d\n",pos - 1,pos);
            }
            pos++;
        }

        while(pos <= n)
            printf("1 %d\n",pos++);

    }

    return true;
}


int main() {
    while(Do());
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论