D. Bear and Two Paths

题目连接：

http://www.codeforces.com/contest/673/problem/D

Description

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.

Input

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).

Output

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.

Sample Input

7 11

2 4 7 3

Sample Output

2 7 1 3 6 5 4

7 1 5 4 6 2 3

题意

给你n和k，表示这个图有n个点，最多k条边

现在让你构造这个图，使得存在两条路径a-v2-...-b,c-v2-...-d恰好都经过n个点

且ab不相邻，cd不相邻

题解：

很显然构造一个蝴蝶的样子就好了，左边一个三角形，右边一个三角形，中间是一条链

这样需要n+1条边就可以了

由于ab不能挨在一起，所以4的时候，是不可行的

代码

#include<bits/stdc++.h>

using namespace std;

int n,k,a,b,c,d;

vector<int>tmp;

int main()

{

    scanf("%d%d",&n,&k);

    scanf("%d%d%d%d",&a,&b,&c,&d);

    if(n==4)return puts("-1"),0;

    if(k<=n)return puts("-1"),0;

    for(int i=1;i<=n;i++)

    {

        if(i==a||i==b||i==c||i==d)continue;

        tmp.push_back(i);

    }

    cout<<a<<" "<<c<<" ";

    for(int i=0;i<tmp.size();i++)cout<<tmp[i]<<" ";

    cout<<d<<" "<<b<<endl;

    cout<<c<<" "<<a<<" ";

    for(int i=0;i<tmp.size();i++)cout<<tmp[i]<<" ";

    cout<<b<<" "<<d<<endl;

}

巴特西

Codeforces Round #351 (VK Cup 2016 Round 3, Div. 2 Edition) D. Bear and Two Paths 构造