CF29E.Quarrel

Friends Alex and Bob live in Bertown. In this town there are n crossroads, some of them are connected by bidirectional roads of equal length. Bob lives in a house at the crossroads number 1, Alex — in a house at the crossroads number n.

One day Alex and Bob had a big quarrel, and they refused to see each other. It occurred that today Bob needs to get from his house to the crossroads n and Alex needs to get from his house to the crossroads 1. And they don't want to meet at any of the crossroads, but they can meet in the middle of the street, when passing it in opposite directions. Alex and Bob asked you, as their mutual friend, to help them with this difficult task.

Find for Alex and Bob such routes with equal number of streets that the guys can follow these routes and never appear at the same crossroads at the same time. They are allowed to meet in the middle of the street when moving toward each other (see Sample 1). Among all possible routes, select such that the number of streets in it is the least possible. Until both guys reach their destinations, none of them can stay without moving.

The guys are moving simultaneously with equal speeds, i.e. it is possible that when one of them reaches some of the crossroads, the other one leaves it. For example, Alex can move from crossroad 1 to crossroad 2, while Bob moves from crossroad 2 to crossroad 3.

If the required routes don't exist, your program should output -1.

朋友亚历克斯（Alex）和鲍勃（Bob）住在贝尔特镇（Bertown）。该镇共有 $n$ 个十字路口，其中某些十字路口由长度相等的双向道路连接。鲍勃住在编号为 $1$ 的十字路口处的房屋中，亚历克斯则住在编号为 $n$ 的十字路口处的房屋中。

某天，亚历克斯和鲍勃发生了激烈的争吵，彼此拒绝见面。恰好今天鲍勃需要从他家（十字路口 $1$）前往十字路口 $n$，而亚历克斯则需要从他家（十字路口 $n$）前往十字路口 $1$。他们希望在整个行程中不在任何一个十字路口相遇，但允许他们在某条道路的中点处迎面相遇（见样例 1）。亚历克斯和鲍勃作为共同的朋友，请你帮助他们解决这一难题。

请为亚历克斯和鲍勃找出两条路径，使得：

• 两条路径包含相同数量的道路段（即边数相等）；
• 两人沿各自路径同时出发、以相同速度行进，在整个过程中永远不会在同一时刻出现在同一个十字路口；
• 允许两人在同一条道路的中点处朝相反方向通过（即“擦肩而过”）；
• 在所有满足条件的路径中，选择道路段总数最少（即路径长度最短）的方案；
• 在两人均未抵达各自目的地前，不允许任何一人停留不动。

注意：两人同步移动且速度相同，因此可能出现这样的情况：当其中一人刚到达某个十字路口时，另一人恰好离开该十字路口。例如，亚历克斯从十字路口 $1$ 移动到十字路口 $2$，而鲍勃同时从十字路口 $2$ 移动到十字路口 $3$。

若不存在满足上述条件的路径，请输出 $-1$。

The first line contains two integers n and m (2 ≤ n ≤ 500, 1 ≤ m ≤ 10000) — the amount of crossroads and the amount of roads. Each of the following m lines contains two integers — the numbers of crossroads connected by the road. It is guaranteed that no road connects a crossroads with itself and no two crossroads are connected by more than one road.

第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 500$，$1 \leq m \leq 10000$）—— 分别表示路口的数量和道路的数量。接下来的 $m$ 行中，每行包含两个整数——表示该道路所连接的两个路口的编号。保证不存在连接某个路口与其自身的道路，且任意两个路口之间至多只有一条道路相连。

If the required routes don't exist, output -1. Otherwise, the first line should contain integer k — the length of shortest routes (the length of the route is the amount of roads in it). The next line should contain k + 1 integers — Bob's route, i.e. the numbers of k + 1 crossroads passed by Bob. The last line should contain Alex's route in the same format. If there are several optimal solutions, output any of them.

如果不存在满足要求的路径，则输出 -1。否则，第一行应包含一个整数 $k$ —— 最短路径的长度（路径长度定义为路径中道路的数量）。第二行应包含 $k+1$ 个整数 —— Bob 的路径，即 Bob 经过的 $k+1$ 个路口的编号。最后一行应以相同格式输出 Alex 的路径。若存在多个最优解，输出任意一个即可。