Codeforces 550 Regular Bridge

题目链接：http://codeforces.com/problemset/problem/550/D

题意：构建一个图，每一个点的最大度数k，至少有一条桥边(去掉该边后图不连通)

思路：很难描述，配合图解释

k为奇数的时候以一条桥边来构建一个对称的图，为了满足黑点度数k构建了k-1个红点，同时为了满足红点的度数构建了1个蓝点，但只有一个蓝点时无法满足蓝点度数k的要求，因此构造了2个互相连接的蓝点，红点与2个蓝点相连，与k-2个红底相连就可以了

k为偶数是无法建图的……输出-1

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 1000030
using namespace std;

int l[maxn],r[maxn];

int main()
{
    int n;
    while (scanf("%d",&n)!=EOF)
    {
        if (n%2==0)
        {
            printf("NO\n");
            continue;
        }
        int cnt=0;
        printf("YES\n");

        for (int i=2;i<=n;i++)
        {
            //printf("1 %d\n",i);
            l[cnt]=1;
            r[cnt++]=i;
        }

        for (int i=2;i<=n;i++)
        {
            for (int j=i;j<=n;j++)
            {
                if (i==j || i+j==n+2)
                 continue;
                //printf("%d %d\n",i,j);
                l[cnt]=i;
                r[cnt++]=j;
            }
        }

        for (int i=2;i<=n;i++)
        {
            //printf("%d %d\n",i,n+1);
            l[cnt]=i;
            r[cnt++]=n+1;
            l[cnt]=i;
            r[cnt++]=n+2;
        }
        if (n>1)
        {
            //printf("%d %d\n",n+1,n+2);
            l[cnt]=n+1;
            r[cnt++]=n+2;
        }
        if (n>1) printf("%d %d\n",2*n+4,cnt*2+1);
        else printf("2 1\n");

        if (n>1) printf("%d %d\n",1,n+3);
        else printf("1 2\n");

        for (int i=0;i<cnt;i++)
        {
            printf("%d %d\n",l[i],r[i]);
            printf("%d %d\n",l[i]+n+2,r[i]+n+2);
        }
    }

}