← 返回题目列表

Codeforces · 643/B

B. 熊和两条路

中文机器翻译题面 查看原题

Bearland 有 n 个城市,编号为 1 到 n。城市通过双向道路连接。每条道路连接两个不同的城市。没有两条道路连接同一对城市。

Bear Limak 曾经在a城市,他想去b城市。由于没有直接的联系,所以他决定长途步行,每个城市都参观一次。正式:

- a 和 b 之间没有道路。
- 存在 n 个不同城市 v1, v2, ..., vn 的序列(路径),其中 v1 = a, vn = b,并且 vi 和 vi + 1 之间存在一条道路,$$i \in \{1, 2, \ldots, n-1\}$$。

前几天,也发生了类似的事情。 Limak 想要在城市 c 和城市 d 之间旅行。它们之间没有道路,但存在一系列 n 个不同的城市 u1, u2, ..., un,u1 = c, un = d,并且 ui 和 ui + 1 之间存在一条道路,对于 $$i \in \{1, 2, \ldots, n-1\}$$。

另外,Limak 认为 Bearland 最多有 k 条路。他想知道自己是否记得正确的一切。

给定 n、k 和四个不同的城市 a、b、c、d,你能找到满足所有给定条件的可能路径 (v1, ..., vn) 和 (u1, ..., un) 吗?找到任何解决方案,如果不可能,则打印 -1。

输入

输入的第一行包含两个整数 n 和 k (4 ≤ n ≤ 1000, n - 1 ≤ k ≤ 2n - 2)——分别是城市数量和允许的最大道路数量。

第二行包含四个不同的整数 a、b、c 和 d (1 ≤ a、b、c、d ≤ n)。

输出

如果不可能满足所有给定条件,则打印 -1。否则,打印两行路径描述。这两行中的第一行应包含 n 个不同的整数 v1, v2, ..., vn,其中 v1 = a 且 vn = b。第二行应包含 n 个不同的整数 u1, u2, ..., un,其中 u1 = c 且 un = d。

两条路径最多生成 2n - 2 条道路:(v1, v2), (v2, v3), ..., (vn - 1, vn), (u1, u2), (u2, u3), ..., (un - 1, un)。如果包含超过 k 条不同的道路或任何其他条件中断,您的答案将被视为错误。请注意,(x, y) 和(y, x) 是同一条道路。

示例

输入 #1

7 11
2 4 7 3

输出 #1

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

输入 #2

1000 999
10 20 30 40

输出 #2

-1

注意

第一个样本测试应该有7个城市,最多11条道路。提供的示例解决方案生成 10 条道路,如图所示。您还可以看到长度 n 在 2 和 4 之间的简单路径,以及长度在 7 和 3 之间的路径。