CF29E Quarrel

朋友 Alex 和 Bob 住在 Bertown 小镇。在这个小镇上有 $n$ 个路口，其中有一些通过等长的双向道路相连。Bob 住在编号为 $1$ 的路口的房子里，而 Alex 住在编号为 $n$ 的路口的房子里。 有一天，Alex 和 Bob 大吵一架，他们拒绝再见面。碰巧今天 Bob 需要从他家到编号为 $n$ 的路口，而 Alex 需要从他家到编号为 $1$ 的路口。他们不想在任何路口碰面，但在逆向通过同一条道路时，可以在路中间相遇。作为他们的共同朋友，他们请你帮忙解决这个难题。 请为 Alex 和 Bob 各自找到一条长度相等的路线，使他们遵循这些路线且始终不会同时出现在同一个路口。他们允许在相向通过同一条道路时在路中间“擦肩而过”（见样例 1）。在所有可能的路线中，请选择使经过道路数最少的一组。直到两人都到达目的地之前，任何一个人都不能停留不动。 他们以相同速度同步移动，也就是说，可能当一个人到达某个路口时，另一个人正好离开该路口。例如，Alex 可以从路口 $1$ 走到路口 $2$ 的同时，Bob 从路口 $2$ 走到路口 $3$。 如果不存在满足要求的路线，你的程序应输出 $-1$。

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 500,\,1 \le m \le 10000$）—— 路口的数量和道路的数量。接下来的 $m$ 行中的每一行包含两个整数，表示一条连接两个路口的道路。保证没有道路连接同一个路口，也没有两条道路连接同一对路口。

如果不存在满足要求的路线，输出 $-1$。否则，第一行输出一个整数 $k$，即最短路线的长度（路线长度为经过的道路数）。第二行输出 $k+1$ 个整数，表示 Bob 的路线，即他经过的 $k+1$ 个路口编号。第三行同样格式输出 Alex 的路线。如果有多种最优方案，输出任意一种均可。

由 ChatGPT 5 翻译