争执AI (CI翻译)
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*$.
朋友 Alex 和 Bob 住在 Bertown。这个城镇有 $*n*$ 个十字路口，其中一些十字路口之间由长度相同的双向道路连接。Bob 住在 1 号十字路口的房子里，Alex 住在 $*n*$ 号十字路口的房子里。AI (CI翻译)
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.
一天，Alex 和 Bob 发生了激烈的争执，他们拒绝见面。碰巧今天 Bob 需要从家前往 $*n*$ 号十字路口，而 Alex 需要从家前往 1 号十字路口。他们不想在任何十字路口相遇，但可以在沿相反方向行驶时于道路中间相遇（见样例 1）。Alex 和 Bob 请你这位共同的朋友帮助他们完成这项艰难的任务。AI (CI翻译)
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.
请为 Alex 和 Bob 找到两条经过相同数量道路的路线，使他们沿着这些路线行进时，不会在同一时刻出现在同一个十字路口。两人可以在相向而行时于道路中间相遇。所有可能的路线中，应选择道路数量最少的方案。在两人都到达目的地之前，任何一人都不能停留不动。AI (CI翻译)
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$.
两人同时以相同速度移动，也就是说，当其中一人到达某个十字路口时，另一人可能正好从该十字路口离开。例如，Alex 可以从十字路口 1 移动到十字路口 2，同时 Bob 从十字路口 2 移动到十字路口 3。AI (CI翻译)
If the required routes don't exist, your program should output -1.
如果不存在满足要求的路线，程序应输出 -1。AI (CI翻译)
Input
输入格式
AI (CI翻译)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 ≤ *n* ≤ 500, 1 ≤ *m* ≤ 10000$），分别表示十字路口的数量和道路的数量。接下来的 $*m*$ 行中，每行包含两个整数，表示由道路连接的两个十字路口的编号。保证没有道路连接一个十字路口自身，且任意两个十字路口之间至多有一条道路。AI (CI翻译)
Output
输出格式
AI (CI翻译)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 的路线。如果有多组最优解，输出任意一组即可。AI (CI翻译)
样例
2 1
1 2
1
1 2
2 1
7 5
1 2
2 7
7 6
2 3
3 4
-1
7 6
1 2
2 7
7 6
2 3
3 4
1 5
6
1 2 3 4 3 2 7
7 6 7 2 1 5 1
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。