朋友亚历克斯和鲍勃住在伯敦。该镇有 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