题目大意：给定k(1≤k≤100)<script type="math/tex" id="MathJax-Element-79">k(1\leq k\leq100)</script>，要求构造一张简单无向连通图，使得存在一个桥，且每一个点的度数都为k<script type="math/tex" id="MathJax-Element-80">k</script>
k<script type="math/tex" id="MathJax-Element-81">k</script>为偶数时无解
证明：
将这个图缩边双，能够得到一棵树
那么一定存在一个叶节点，仅仅连接一条桥边
那么这个边双内部全部点度数之和为偶数 除掉连出去的桥边外度数之和为奇数 故不合法
然后k<script type="math/tex" id="MathJax-Element-82">k</script>为奇数的时候我们仅仅须要构造两个对称的边双被一条桥边连接的图即可了
因为每一个点度数为k<script type="math/tex" id="MathJax-Element-83">k</script>。因此每一边至少须要k+1<script type="math/tex" id="MathJax-Element-84">k+1</script>个点
可是k+1<script type="math/tex" id="MathJax-Element-85">k+1</script>个点奇偶性不合法。因此每一边至少须要k+2<script type="math/tex" id="MathJax-Element-86">k+2</script>个点
如今问题转化成了给定一个度数数组要求构造一张原图
这个在Wc2015讲过 每次找剩余的度数最大的点
如果这个点的度数为d<script type="math/tex" id="MathJax-Element-87">d</script> 那么仅仅须要向其他度数最大的d<script type="math/tex" id="MathJax-Element-88">d</script>个点连边即可

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 110
using namespace std;
struct edge{
    int x,y;
    edge() {}
    edge(int _,int __):
        x(_),y(__) {}
}stack[10100];
int k,top;
int degree[M],a[M];
bool Compare(int x,int y)
{
    return degree[x] > degree[y] ;
}
int main()
{
    int i,j;
    cin>>k;
    if(~k&1)
        return puts("NO"),0;
    puts("YES");
    if(k==1)
        return puts("2 1\n1 2"),0;
    cout<<(k+2<<1)<<‘ ‘<<((k+2)*k)<<endl;
    int n=k+2;
    for(degree[1]=k-1,i=2;i<=n;i++)
        degree[i]=k;
    for(i=1;i<=n;i++)
        a[i]=i;
    for(i=1;i<=n;i++)
    {
        sort(a+1,a+n+1,Compare);
        for(j=2;j<=degree[a[1]]+1;j++)
        {
            stack[++top]=edge(a[1],a[j]);
            degree[a[j]]--;
        }
        degree[a[1]]=0;
    }
    for(i=1;i<=top;i++)
    {
        printf("%d %d\n",edges[i].x,edges[i].y);
        printf("%d %d\n",edges[i].x+n,edges[i].y+n);
    }
    printf("%d\n",1,n+1);
    return 0;
}