← 返回题目列表

Codeforces · 29/E

E. 争吵

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

朋友亚历克斯和鲍勃住在伯敦。该镇有 n 个十字路口,其中一些十字路口由等长的双向道路连接。鲍勃住在 1 号十字路口的一所房子里,亚历克斯住在 n 号十字路口的一所房子里。

有一天,亚历克斯和鲍勃大吵了一架,他们拒绝见面。碰巧今天鲍勃需要从他的家到十字路口n,而亚历克斯需要从他的家到十字路口1。他们不想在任何十字路口相遇,但他们可以在街道中间相遇,当从相反的方向经过它时。亚历克斯和鲍勃请求你,作为他们共同的朋友,帮助他们完成这项艰巨的任务。

为亚历克斯和鲍勃找到街道数量相同的路线,使他们可以沿着这些路线行驶,并且永远不会同时出现在同一个十字路口。当他们走向对方时,他们可以在街道中间相遇(参见示例 1)。在所有可能的路线中,选择其中的街道数量尽可能少的路线。直到两人到达目的地之前,谁都不能原地踏步。

这些家伙同时以相同的速度移动,也就是说,当其中一个到达某个十字路口时,另一个可能会离开它。例如,Alex 可以从十字路口 1 移动到十字路口 2,而 Bob 可以从十字路口 2 移动到十字路口 3。

如果所需的路由不存在,您的程序应该输出-1。

输入

第一行包含两个整数 n 和 m (2 ≤ n ≤ 500, 1 ≤ m ≤ 10000) — 十字路口的数量和道路的数量。接下来的 m 行中的每一行都包含两个整数——道路连接的十字路口的数量。保证没有道路将十字路口与其自身连接,并且没有两个十字路口由多于一条道路连接。

输出

如果所需的路由不存在,则输出-1。否则,第一行应包含整数 k — 最短路线的长度(路线的长度是其中的道路数量)。下一行应包含 k + 1 个整数——Bob 的路线,即 Bob 经过的 k + 1 个十字路口的数量。最后一行应包含相同格式的 Alex 的路线。如果有多个最优解,则输出其中任意一个。

示例

输入 #1

2 1
1 2

输出 #1

1
1 2
2 1

输入 #2

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

输出 #2

-1

输入 #3

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

输出 #3

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