I found an interesting problem on https://codeforces.com/problemset/problem/643/B:
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...

I tried it in Python, but could not do it. Can you solve it?
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)
    return
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)