Bearland has n cities, numbered 1 through n. Cities are connected via bidirectional roads. Each road connects two distinct cities. No two roads connect the same pair of cities.
Bear Limak was once in a city a and he wanted to go to a city b. There was no direct connection so he decided to take a long walk, visiting each city exactly once. Formally:
- There is no road between a and b.
- There exists a sequence (path) of n distinct cities
v1, v2, ..., vn that
v1 = a,
vn = b and there is a road between
vi and
vi + 1 for
.
On the other day, the similar thing happened. Limak wanted to travel between a city
c and a city d. There is no road between them but there exists a sequence of
n distinct cities u1, u2, ..., un that
u1 = c,
un = d and there is a road between
ui and
ui + 1 for
.
Also, Limak thinks that there are at most k roads in Bearland. He wonders whether he remembers everything correctly.
Given n, k and four distinct cities a, b, c, d, can you find possible paths (v1, ..., vn) and (u1, ..., un) to satisfy all the given conditions? Find any solution or print -1 if it's impossible.
The first line of the input contains two integers n and k (4 ≤ n ≤ 1000, n - 1 ≤ k ≤ 2n - 2) — the number of cities and the maximum allowed number of roads, respectively.
The second line contains four distinct integers a, b, c and d (1 ≤ a, b, c, d ≤ n).
Print -1 if it's impossible to satisfy all the given conditions. Otherwise, print two lines with paths descriptions. The first of these two lines should contain n distinct integers v1, v2, ..., vn where v1 = a and vn = b. The second line should contain n distinct integers u1, u2, ..., un where u1 = c and un = d.
Two paths generate at most 2n - 2 roads: (v1, v2), (v2, v3), ..., (vn - 1, vn), (u1, u2), (u2, u3), ..., (un - 1, un). Your answer will be considered wrong if contains more than k distinct roads or any other condition breaks. Note that (x, y) and (y, x) are the same road.
7 11 2 4 7 3
2 7 1 3 6 5 4 7 1 5 4 6 2 3
1000 999 10 20 30 40
-1
In the first sample test, there should be 7 cities and at most 11 roads. The provided sample solution generates 10 roads, as in the drawing. You can also see a simple path of length n between 2 and 4, and a path between 7 and 3.
题意：
有1-n个城市，有个人想从a到b城市，但是a到b没有直接相连的道路，所以他想经过所有城市1次后再到b，同样，c到的城市也是这样。a,b,c,d,四个城市是不同的。道路最多要k条，找出符合条件的两条路径。所有的路是双向的。
分析：
要想选择的路尽量的少，那么除了四个点之外的其他点要连在一起，这样最优。最少需要n+1条路。
如果有n=4，k<=n显然是不可以的。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a,b,c,d,n,k;
cin>>n>>k>>a>>b>>c>>d;
if(n==4||k<=n){
cout<<"-1";return 0;
}
cout<<a<<' '<<c;
for(int i=1;i<=n;i++){
if(i!=a&&i!=b&&i!=c&&i!=d)cout<<' '<<i;
}
cout<<' '<<d<<' '<<b<<endl;
cout<<c<<' '<<a;
for(int i=1;i<=n;i++)
if(i!=a&&i!=b&&i!=c&&i!=d)cout<<' '<<i;
cout<<' '<<b<<' '<<d<<endl;
return 0;
}