codeforces 22 C. System Administrator
http://codeforces.com/contest/22/problem/C 题意：要求用n个点m条边构造一个不允许有重边的图，满足当去掉点v的时候，剩下的n-1个不联通。如果有答案输出任意，没答案输出-1. 思路：首先如果n个点要联通。。至少有n-1条边，此时为一棵树。但是是不是边越多越好呢？显然是不可以的。满足去掉一个点使得n-1个点不联通的情况为，存在一个点u只和v相连，不和任意任何其他点相连，那么当去掉v点，u点就变成不可到达了。边数最多的情况就是，除了v点以外的n-1个点，每个点的度都是n-2(去掉自身以及u点还有n-2个点)，，那么除去u点以外的n-1个点的度数就是（n-1）(n-2)，边数则为(n-1)(n-2)/2，再加一条连接u的边，所以图的最大边数为(n-1)*(n-2)/2+1，最小为n-1.
如果有解，那么接下来的问题是构造。
我是按照如下方式构造的：
先构造一条链，将u点放在第一个，v点放在第二个。不妨当v=1时令u=2,否则u=1;
m-=n-1,如果m还有剩余，那么从第二个点开始，一直到第n-2个点，每个点与至少隔1个点的其他点相连，直到边数没有剩余。
1/* ***********************************************
2Author :111qqz
3Created Time :2015年12月30日 星期三 20时36分06秒
4File Name :code/cf/problem/22C.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E5+7;
34int n,m,v;
35int a[N];
36int main()
37{
38 #ifndef ONLINE_JUDGE
39 freopen("code/in.txt","r",stdin);
40 #endif
41 cin>>n>>m>>v;
42 if (m<n-1||m>((n-1)*(n-2)/2+1))
43 {
44 puts("-1");
45 return 0;
46 }
47
48 for ( int i = 1 ; i <= n ; i++)
49 {
50 a[i] = i ;
51 if (i==2)
52 {
53 a[i]=v;
54 }
55 if (i==v)
56 {
57 a[i]=2;
58 }
59 }
60 for ( int i = 1 ; i <= n-1 ; i++)
61 {
62 printf("%d %d\n",a[i],a[i+1]);
63 }
64 m-=n-1;
65
66 int cnt = 0 ;
67 for ( int i = 2 ; i <= n-2 ; i ++)
68 {
69 if (cnt>m) break;
70 for ( int j = i+2 ; j <= n ; j++)
71 {
72 cnt++;
73 if (cnt>m) break;
74 printf("%d %d\n",a[i],a[j]);
75 }
76 }
77
78
79 #ifndef ONLINE_JUDGE
80 fclose(stdin);
81 #endif
82 return 0;
83}