2647: 第三饭堂
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：6
解决：1
题目描述
由于领导们发现第二饭堂各种和谐，所以他们决定转战高居山顶的第三饭堂。
而在第三饭堂用完餐的小A和小B，要到二饭旁的水果店买水果。重要的是，在途中遇到领导这种事是他们所不愿看见的。
已知从三饭到二饭有n个路口，从1~n编号。小A和小B在1号路口，想到n号路口买水果；领导们在n号路口，想到1号路口去巡视。每个时刻，小A和小B总是一起行动，领导们也都一起行动，双方都会从当前所在路口，走到某个与之相邻的路口，不会原地停留。双方可以同时在一条路上往不同方向走，但某个时刻双方不可以同时停留在某个路口中。
为了节省时间，请你告诉他们，最早在什么时刻，他们能同时到达目的地，并告诉他们具体路线是什么？
输入
第一行包含两个整数 n，m (,) 表示一共有n个路口，m条马路。
接下来m行每行包含两个整数x，y，表示x路口和y路口有马路相连。
输出
第一行输出一个整数k，表示他们最早到达目的地的时刻。
第二行依次输出k个整数，表示小A和小B的行走路线。
第三行依次输出k个整数，表示领导们的行走路线。
若无解，则输出-1。
样例输入 复制
2 1
1 2样例输出 复制
1
1 2
2 1 提示
|
Quarrel.in |
Quarrel.out |
|
7 5 1 2 2 7 7 6 2 3 3 4 |
-1 |
|
Quarrel.in |
Quarrel.out |
|
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 |
对于40%的数据，n≤100；
对于100%的数据，2≤n≤500，1≤m≤10000。