题目描述

诸葛亮，字孔明，想要恢复汉室的力量。

在统一蜀汉之后，他计划对曹魏发动北伐。中国由 N 个领土和 M 条双向道路组成，每条道路都需要 1 天通过。形式化地说，这是一张无权、无向、允许重边与自环的多重图。

诸葛亮的军队当前位于领土 S，目标是到达领土 T，只能沿道路行军。

然而，在行军过程中的某一时刻，当军队位于某个领土时，敌军可能会永久封锁其中一条道路。这种事情至多发生一次，并且会在敌方将领自行选择的最坏时刻、最坏地点发生。道路一旦被封锁，之后就再也不能通过。

由于诸葛亮拥有强大的情报网络，一旦道路被封锁，他会立刻得知是哪一条路被封锁，并可以立即调整之后前往 T 的路线。

因此，诸葛亮希望在出发前先选定一条初始路线，使得在“敌人以最坏方式封锁一条边”的情况下，总行军时间的最坏值尽可能小。

中国的领土和道路非常多，求出这样的最优路线并不容易。请你编写程序 foresight.cpp 来解决这个问题。

输入格式

第一行输入四个整数 N, M, S, T，分别表示领土数、道路数、起点领土和终点领土。

接下来 M 行，每行输入两个整数 A_i, B_i，表示第 i 条道路连接的两个领土。

输出格式

• 如果不存在任何一种初始路线，能够保证无论敌军封锁哪一条边，都仍然可以到达 T，输出 -1。
• 否则：
  • 第一行输出两个整数：
    • 最坏情况下可能需要的最小总行军时间；
    • 你输出的初始路线长度（不要求这条路线本身长度最短）。
  • 第二行按经过顺序输出这条初始路线上的所有领土编号。第一项必须是 S，最后一项必须是 T。

如果有多条最优初始路线，输出任意一条即可。

数据范围

• 1 ≤ N ≤ 10^5
• 0 ≤ M ≤ 10N
• 0 ≤ S, T, A_i, B_i < N

子任务与评分

样例 1

输入

7 10 0 6
0 1
0 2
1 1
1 3
2 3
3 4
3 4
4 5
4 6
5 6

输出

6 4
0 1 3 4 6

样例 2

输入

3 3 0 2
0 1
1 2
1 0

输出

-1

样例解释

在第一个样例中，一条最优的初始路线是：

0 → 1 → 3 → 4 → 6

最坏情况下，在走完 0 → 1 后，敌人会封锁边 1 - 3。这时诸葛亮必须改走：

1 → 0 → 2 → 3 → 4 → 6

于是总行程长度为 6。

在第二个样例中，边 1 - 2 可能会被封锁，从而使得到达顶点 2 不再可能。