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_1, v_2, ..., v_{n} that v_1 = a, v_{n} = b and there is a road between v_{i} and v_{i} + 1 for $i \in \{1,2, \ldots, n - 1 \}$. 

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_1, u_2, ..., u_{n} that u_1 = c, u_{n} = d and there is a road between u_{i} and u_{i} + 1 for $i \in \{1,2, \ldots, n - 1 \}$.

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_1, ..., v_{n}) and (u_1, ..., 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_1, v_2, ..., v_{n} where v_1 = a and v_{n} = b. The second line should contain n distinct integers u_1, u_2, ..., u_{n} where u_1 = c and u_{n} = d.

Two paths generate at most 2n - 2 roads: (v_1, v_2), (v_2, v_3), ..., (v_{n} - 1, v_{n}), (u_1, u_2), (u_2, u_3), ..., (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.


-----Examples-----
Input
7 11
2 4 7 3

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

Input
1000 999
10 20 30 40

Output
-1



-----Note-----

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.

 [Image]

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Constructive algorithms

Starter code:

Solutions:
(n, k) = map(int, input().split())
(a, b, c, d) = map(int, input().split())
if n == 4:
	print(-1)
	exit()
if k < n + 1:
	print(-1)
	exit()
vertices = set([i for i in range(1, n + 1)])
vertices.remove(a)
vertices.remove(b)
vertices.remove(c)
vertices.remove(d)
lst = []
lst.append(a)
lst.append(c)
for x in vertices:
	lst.append(x)
lst.append(d)
lst.append(b)
print(*lst)
print(lst[1], lst[0], end=' ')
print(*lst[2:-2], end=' ')
print(lst[-1], lst[-2])


import math
import sys
from collections import Counter

def solve():
	(n, k) = [int(x) for x in input().split()]
	(a, b, c, d) = [int(x) for x in input().split()]
	if k <= n or n < 5:
		print(-1)
		return None
	S = list(range(1, n + 1))
	S.remove(a)
	S.remove(b)
	S.remove(c)
	S.remove(d)
	A = [a, c] + S + [d, b]
	B = [c, a] + S + [b, d]
	print(' '.join(map(str, A)))
	print(' '.join(map(str, B)))
solve()


(n, k) = map(int, input().split())
(a, b, c, d) = map(int, input().split())
if k - n > 0 and n != 4:
	print(a, c, end=' ')
	for i in range(1, n + 1):
		if i != a and i != b and (i != d) and (i != c):
			print(i, end=' ')
	print(d, b)
	print(c, a, end=' ')
	for i in range(1, n + 1):
		if i != a and i != b and (i != d) and (i != c):
			print(i, end=' ')
	print(b, d)
else:
	print(-1)


(n, k) = list(map(int, input().split()))
(a, b, c, d) = list(map(int, input().split()))
if n == 4 or k < n + 1:
	print(-1)
	exit()
extra = 1
while extra == a or extra == b or extra == c or (extra == d):
	extra += 1
v = [a, c, extra, d]
k = extra + 1
while k <= n:
	if k != a and k != b and (k != c) and (k != d) and (k != extra):
		v.append(k)
	k += 1
v.append(b)
print(*v)
u = [c, a, extra] + list(reversed(v[3:]))
print(*u)


(n, k) = list(map(int, input().split()))
(a, b, c, d) = input().split()
if n < 5 or k < n + 1:
	print(-1)
else:
	l = list(set(map(str, list(range(1, n + 1)))) - {a, b, c, d})
	print(' '.join([a, c] + l + [d, b] + [c, a] + l + [b, d]))


f = lambda : map(int, input().split())
(n, k) = f()
(a, b, c, d) = f()
s = list(set(range(1, n + 1)).difference({a, b, c, d}))
d = [a, c] + s + [d, b] + [c, a] + s + [b, d]
print(' '.join(map(str, d)) if 4 < n < k else -1)


(n, k) = map(int, input().split())
l = [int(x) for x in input().split()]
if n == 4 or k <= n:
	print(-1)
	quit()
p = []
for i in range(1, n + 1):
	if i not in l:
		p.append(i)
print(l[0], l[2], end=' ')
for i in p:
	print(i, end=' ')
print(l[3], l[1])
print(l[2], l[0], end=' ')
for i in p:
	print(i, end=' ')
print(l[1], l[3])


(n, k) = map(int, input().split())
(a, b, c, d) = map(int, input().split())
if n == 4:
	print(-1)
	exit()
if k < n + 1:
	print(-1)
	exit()
print(f'{a} {c}', end=' ')
for i in range(1, n + 1):
	if i not in (a, b, c, d):
		print(i, end=' ')
print(f'{d} {b}')
print(f'{c} {a}', end=' ')
for i in range(1, n + 1):
	if i not in (a, b, c, d):
		print(i, end=' ')
print(f'{b} {d}')


(n, k) = map(int, input().split())
(a, b, c, d) = map(int, input().split())
if k <= n or n == 4:
	print(-1)
	exit()
ans = [a, c] + [i for i in range(1, n + 1) if i not in [a, b, c, d]] + [d, b]
print(*ans)
ans2 = [c, a] + [i for i in range(1, n + 1) if i not in [a, b, c, d]] + [b, d]
print(*ans2)


(n, k) = [int(i) for i in input().split()]
(a, b, c, d) = [int(i) for i in input().split()]
if k < n + 1 or n == 4:
	print(-1)
else:
	s = []
	for i in range(1, n + 1):
		if i != a and i != b and (i != c) and (i != d):
			s.append(i)
	q = [a] + [c] + s + [d] + [b]
	w = [c] + [a] + s + [b] + [d]
	print(*q)
	print(*w)


(n, k) = map(int, input().split())
(a, b, c, d) = map(int, input().split())
notUse = [a, b, c, d]
if n >= k or n == 4:
	print(-1)
	exit()
f = [a, c]
cntr = 0
for i in range(n - 4):
	cntr += 1
	while cntr in notUse:
		cntr += 1
	f.append(cntr)
f += [d, b]
bk = [c, a]
cntr = 0
for i in range(n - 4):
	cntr += 1
	while cntr in notUse:
		cntr += 1
	bk.append(cntr)
bk += [b, d]
print(' '.join(map(str, f)))
print(' '.join(map(str, bk)))


import sys
import math
import itertools as it
import operator as op
import fractions as fr
(n, k) = map(int, sys.stdin.readline().split())
(a, b, c, d) = map(int, sys.stdin.readline().split())
if k < n + 1 or n == 4:
	print(-1)
else:
	path = list(set(range(1, n + 1)).difference([a, b, c, d]))
	print(' '.join(map(str, [a, c] + path + [d, b])))
	print(' '.join(map(str, [c, a] + path + [b, d])))


from __future__ import print_function
from __future__ import unicode_literals
from __future__ import division
from __future__ import absolute_import
import math
import string
import itertools
import fractions
import heapq
import collections
import re
import array
import bisect

def pp(p):
	print(' '.join([str(i) for i in p]))

def cpath():
	if l == 2:
		ps = [i for i in range(1, n + 1) if i not in (a, b, c, d)]
		path1 = [a] + ps + [b]
		if a != c:
			path2 = path1[::-1]
		else:
			path2 = path1
	elif l == 3:
		rb = [False, False]
		if a == c:
			(x, y, z) = (a, b, d)
		elif a == d:
			(x, y, z) = (a, b, c)
			rb[1] = True
		elif b == c:
			(x, y, z) = (b, a, d)
			rb[0] = True
		else:
			(x, y, z) = (b, a, c)
			rb = [True, True]
		ps = [i for i in range(1, n + 1) if i not in (a, b, c, d)]
		path1 = [x] + ps + [z] + [y]
		if rb[0]:
			path1 = path1[::-1]
		path2 = [x] + ps + [y] + [z]
		if rb[1]:
			path2 = path2[::-1]
	else:
		path1 = [a, c] + [i for i in range(1, n + 1) if i not in (a, b, c, d)] + [d, b]
		path2 = [c, a] + [i for i in range(1, n + 1) if i not in (a, b, c, d)] + [b, d]
	pp(path1)
	pp(path2)
(n, k) = map(int, input().split(' '))
(a, b, c, d) = map(int, input().split(' '))
l = len(set([a, b, c, d]))
if k < n + l - 3:
	print(-1)
elif n == 4:
	if l <= 3:
		cpath()
	else:
		print(-1)
else:
	cpath()


def main():
	(n, k) = [int(i) for i in input().strip().split()]
	(a, b, c, d) = [int(i) for i in input().strip().split()]
	if k <= n or n <= 4:
		print(-1)
		return
	s = [a, b, c, d]
	others = [i for i in range(1, n + 1) if i not in s]
	print(' '.join(map(str, [a, c] + others + [d, b])))
	print(' '.join(map(str, [c, a] + others + [b, d])))
main()


import sys
(n, k) = map(int, input().split())
(a, b, c, d) = map(int, input().split())
if k < n + 1 or n == 4:
	print(-1)
	sys.exit()
ans = [a, c]
l = [i for i in range(1, n + 1) if i != a and i != b and (i != c) and (i != d)]
for i in l:
	ans.append(i)
ans.extend([d, b])
for i in ans:
	print(i, end=' ')
print()
(ans[0], ans[1]) = (ans[1], ans[0])
(ans[n - 2], ans[n - 1]) = (ans[n - 1], ans[n - 2])
for i in ans:
	print(i, end=' ')
print('\n')


(n, k) = map(int, input().split())
(a, b, c, d) = map(int, input().split())
i = 1
path = []
while i <= n:
	if i != a and i != b and (i != c) and (i != d):
		path.append(i)
	i += 1
ab = [str(x) for x in [a, c] + path + [d, b]]
cd = [str(x) for x in [c, a] + path + [b, d]]
if n == 4 or k <= n:
	print('-1')
else:
	print(' '.join(ab))
	print(' '.join(cd))


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, k) = map(int, input().split())
(a, b, c, d) = map(int, input().split())
if k < n + 1 or n == 4:
	print('-1')
	exit(0)
l = [_ for _ in range(1, n + 1)]
l.remove(a)
l.remove(b)
l.remove(c)
l.remove(d)
print(a, end=' ')
print(c, end=' ')
for x in l:
	print(x, end=' ')
print(d, end=' ')
print(b, end=' ')
print('')
print(c, end=' ')
print(a, end=' ')
for x in l:
	print(x, end=' ')
print(b, end=' ')
print(d, end=' ')


(n, k) = map(int, input().split())
(a, b, c, d) = map(int, input().split())
if k < n + 1 or n == 4:
	print(-1)
	exit()
v = [0 for i in range(n + 1)]
v[a] = v[b] = v[c] = v[d] = 1
e = f = 0
for i in range(1, n + 1):
	if not v[i] and (not e):
		e = i
		v[i] = 1
		continue
	if not v[i] and e and (not f):
		f = i
		v[i] = 1
if n == 5:
	print(a, c, e, d, b, sep=' ')
	print(c, a, e, b, d, sep=' ')
	exit()
a1 = [a, c, e]
for i in range(1, n + 1):
	if not v[i]:
		a1.append(i)
a1 += [f, d, b]
a2 = [c, a, e]
for i in range(1, n + 1):
	if not v[i]:
		a2.append(i)
a2 += [f, b, d]
print(' '.join(map(str, a1)))
print(' '.join(map(str, a2)))


(n, k) = map(int, input().split())
(a, b, c, d) = map(int, input().split())
B = []
for i in range(1, n + 1):
	if i not in (a, b, c, d):
		B.append(i)
	else:
		i -= 1
A = [a, c] + B + [d, b]
C = [c, a] + B + [b, d]
R = set()
for i in range(n - 1):
	R.add(tuple(sorted((A[i], A[i + 1]))))
	R.add(tuple(sorted((C[i], C[i + 1]))))
if tuple(sorted((a, b))) in R:
	print(-1)
	exit()
if tuple(sorted((c, d))) in R:
	print(-1)
	exit()
if len(R) > k:
	print(-1)
	exit()
print(*A)
print(*C)


(n, k) = map(int, input().split())
(a, b, c, d) = map(int, input().split())
ok = 0
L = [i + 1 for i in range(n)]
D = [a, b, c, d]
D.sort(reverse=True)
for i in range(4):
	del L[D[i] - 1]
if n == 4 or n >= k:
	print(-1)
else:
	print(str(a) + ' ' + str(c), end=' ')
	for i in range(n - 4):
		print(L[i], end=' ')
	print(str(d) + ' ' + str(b))
	print(str(c) + ' ' + str(a), end=' ')
	for i in range(n - 4):
		print(L[i], end=' ')
	print(str(b) + ' ' + str(d))


import sys
print = sys.stdout.write
(n, k) = map(int, input().split())
(a, b, c, d) = map(int, input().split())
if n == 4 or k < n + 1:
	print('-1\n')
	exit()
E = (a, b, c, d)
print(f'{a} {c} ')
for i in range(1, n + 1):
	if i not in E:
		print(f'{i} ')
print(f'{d} {b}\n')
print(f'{c} {a} ')
for i in range(1, n + 1):
	if i not in E:
		print(f'{i} ')
print(f'{b} {d}\n')


def main():
	(n, k) = (int(x) for x in input().split())
	(a, b, c, d) = (int(x) for x in input().split())
	(path1, path2) = solver(n, k, a, b, c, d)
	if path1 == None:
		print(-1)
	else:
		for x in path1:
			print(x, end=' ')
		print()
		for x in path2:
			print(x, end=' ')

def solver(n, k, a, b, c, d):
	if k <= n or n == 4:
		return (None, None)
	else:
		path1 = [a, c] + [i for i in range(1, n + 1) if i not in (a, b, c, d)] + [d, b]
		path2 = [c, a] + [i for i in range(1, n + 1) if i not in (a, b, c, d)] + [b, d]
		return (path1, path2)
main()


ip = lambda : map(int, input().split())
(n, k) = ip()
(a, b, c, d) = ip()
if k - n + 1 < 2 or n == 4:
	print(-1)
else:
	P = []
	for i in range(1, n + 1):
		if i not in [a, b, c, d]:
			P.append(i)
	P1 = [a] + P[1:] + [c, P[0], d, b]
	P2 = [c] + P[-1:0:-1] + [a, P[0], b, d]
	print(*P1)
	print(*P2)


(n, k) = input().split(' ')
n = int(n)
k = int(k)
(a, b, c, d) = input().split(' ')
(a, b, c, d) = (int(a), int(b), int(c), int(d))
if k <= n:
	print(-1)
	exit()
if n == 4:
	print(-1)
	exit()
city = list(range(1, n + 1))
road = [a, c]
for i in range(len(city)):
	if city[i] not in (a, b, c, d):
		road.append(city[i])
road += [d, b]
t = ''
print(' '.join(('{0}'.format(t) for t in road)))
road = [c, a] + road[2:n - 2] + [b, d]
print(' '.join(('{0}'.format(t) for t in road)))