C. System Administrator
time limit per test
memory limit per test
input
output
Bob got a job as a system administrator in X corporation. His first task was to connect n servers with the help of m two-way direct connection so that it becomes possible to transmit data from one server to any other server via these connections. Each direct connection has to link two different servers, each pair of servers should have at most one direct connection. Y corporation, a business rival of X corporation, made Bob an offer that he couldn't refuse: Bob was asked to connect the servers in such a way, that when server with index v
Input
The first input line contains 3 space-separated integer numbers n, m, v (3 ≤ n ≤ 105, 0 ≤ m ≤ 105, 1 ≤ v ≤ n), n — amount of servers, m— amount of direct connections, v
Output
If it is impossible to connect the servers in the required way, output -1. Otherwise output m
Examples
input
5 6 3
output
1 2
2 3
3 4
4 5
1 3
3 5
input
6 100 1
output
-1
首先必须得是连通图，所以m >= n - 1并且存在割点 所以m <= (n - 2) * (n - 1) / 2 + 1(把一个点分离出去，剩下所有点组成完全图，在把剩下的一个点连到割点上)剩下的点随意分配;
#include <bits/stdc++.h>
#define maxn 100005
#define MOD 1000000007
using namespace std;
typedef long long ll;
int num[maxn];
int main(){
// freopen("in.txt", "r", stdin);
int n, m, v;
scanf("%d%d%d", &n, &m, &v);
if(m < n - 1 || m > (ll)(n - 2) * (n - 1) / 2 + 1){
puts("-1");
return 0;
}
for(int i = 1; i <= n; i++){
num[i] = i;
}
if(v != 2){
swap(num[2], num[v]);
}
for(int i = 1; i < n; i++){
printf("%d %d\n", num[i], num[i+1]);
}
m -= n - 1;
for(int i = 2; i < n; i++){
for(int j = i+2; j <= n; j++){
if(m == 0)
return 0;
printf("%d %d\n", num[i], num[j]);
m--;
}
}
return 0;
}