题目描述

Bajtazar 刚刚从采矿学院毕业，开始在地下洞穴中开采珍贵的回声水晶。

然而，他不小心惊动了一只 Warden。

地下洞穴由 $n$ 个洞室和 $m$ 条走廊构成。通过任意一条走廊都恰好需要 1 分钟。

Bajtazar 当前位于洞室 $1$。

Warden 最开始出现在洞室 $w$。

洞室 $n$ 中有一部通往地面的电梯。只要 Bajtazar 进入电梯，就能够逃离 Warden。

Warden 的力量值为 $p$。

一次蓄力恰好持续 1 分钟。在这一分钟中，Bajtazar 可以：

• 沿一条走廊移动到相邻洞室；
• 或者留在当前洞室不动。

一分钟结束时，Warden 发动攻击。

设此时 Warden 与 Bajtazar 之间的最短路距离为 $k$。

情况 1：$k<p$

Warden 释放声波攻击，Bajtazar 受到

$p-k$

点伤害。

此时 Warden 的位置不发生变化。

情况 2：$k\ge p$

Bajtazar 已经位于正常声波攻击范围之外。

此时 Warden 会直接瞬移到 Bajtazar 当前所在的洞室，并使 Bajtazar 受到完整的

$p$

点伤害。

随后，Warden 从这个新的位置开始下一轮蓄力。

上述过程每分钟重复一次，直到 Bajtazar 到达洞室 $n$ 中的电梯。

注意：

• 打开电梯门几乎不需要时间；
• 但是 Bajtazar 到达洞室 $n$ 的这一分钟结束时，仍然会承受最后一次 Warden 攻击；
• Bajtazar 的移动总是发生在两次攻击之间。

Bajtazar 有足够多的恢复道具，因此不必考虑死亡问题。

你的任务是为 Bajtazar 选择移动方案，使他从洞室 $1$ 到达洞室 $n$ 的过程中受到的总伤害最小。

输入格式

第一行包含四个整数 $n,m,w,p$：

• $2\le n\le10^5$；
• $1\le m\le3\cdot10^5$；
• $1\le w\le n$；
• $1\le p\le10^9$。

其中：

• $n$ 为洞室数；
• $m$ 为走廊数；
• $w$ 为 Warden 的初始位置；
• $p$ 为 Warden 的力量值。

接下来 $m$ 行，每行包含两个整数 $u,v$：

$1\le u,v\le n$，

表示洞室 $u$ 与 $v$ 之间有一条双向走廊。

保证整张图：

• 连通；
• 无自环；
• 无重边。

输出格式

输出一个整数，表示 Bajtazar 到达电梯前受到的最小可能总伤害。

样例

8 9 3 3
1 2
2 3
2 4
3 4
3 5
4 6
5 7
6 7
7 8

9

样例说明

一种最优路线依次到达：

$2,4,6,7,8$。

Bajtazar 在到达这些洞室后的攻击中分别受到：

$2,2,1,1,3$

点伤害，总计

$2+2+1+1+3=9$。

最后一次受到 3 点伤害，是因为到达洞室 $8$ 后 Warden 发生了瞬移。

如果删去洞室 $8$，也就是把原来的洞室 $7$ 作为电梯所在地，那么答案会变为 6，并且过程中 Warden 不会发生瞬移。

子任务

子任务	附加限制	分值
1	$n\le10$	15
2	$n\le1000$	25
3	$w=1$	20
4	$p\ge n$
5	无额外限制