CodeForces 673D Bear and Two Paths（构造）

思路：构造，显然是一个蝴蝶形状的图

#include<bits\stdc++.h>
using namespace std;

int main()
{
	int n,k,a,b,c,d;
	vector<int>g;
	scanf("%d%d",&n,&k);
	scanf("%d%d%d%d",&a,&b,&c,&d);
	if(n==4)
	{
		puts("-1");
		return 0;
	}
	if (k<=n)
	{
		puts("-1");
		return 0;
	}
	for (int i = 1;i<=n;i++)
	{
		if(i==a||i==b||i==c||i==d)
			continue;
		g.push_back(i);
	}
	printf("%d %d ",a,c);
	for (int i = 0;i<g.size();i++)
		printf("%d ",g[i]);
	printf("%d %d\n",d,b);
	printf("%d %d ",c,a);
	for (int i = 0;i<g.size();i++)
		printf("%d ",g[i]);
	printf("%d %d\n",b,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 v₁,?v₂,?...,?v_n that v₁?=?a, v_n?=?b and there is a road between v_i and v_i?+?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 u₁,?u₂,?...,?u_n that u₁?=?c, u_n?=?d and there is a road between u_i and u_i?+?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 (v₁,?...,?v_n) and (u₁,?...,?u_n) 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 v₁,?v₂,?...,?v_n where v₁?=?a and v_n?=?b. The second line should contain n distinct integersu₁,?u₂,?...,?u_n where u₁?=?c and u_n?=?d.

Two paths generate at most 2n?-?2 roads: (v₁,?v₂),?(v₂,?v₃),?...,?(v_n?-?1,?v_n),?(u₁,?u₂),?(u₂,?u₃),?...,?(u_n?-?1,?u_n). 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

2 7 1 3 6 5 4
7 1 5 4 6 2 3

1000 999
10 20 30 40

-1