L-爆破鸭科夫_2025年华南理工大学程序设计竞赛（秋季赛）

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

走地鸡 $SCUTkk$ 曾在机缘巧合之下落到了鸭科夫中，并想方设法成功的逃了出去，在离开前，它在鸭科夫的**某些点以及唯一的出口上**放置了一些**倒计时各自独立**的定时炸弹，并在离开鸭科夫后启动了所有炸弹的倒计时。每个点上**至多存在一个**炸弹。

作为鸭兵大统领的你奉命追查 $SCUTkk$ 的下落，此时正在 $SCUTkk$ 落入鸭科夫时的起点处调查。

虽然鸭科夫是一张有向图，但你是鸭科夫的鸭兵大统领，拥有特权可以 **无视边的方向** 进行 **瞬间移动** 。即对你来说，鸭科夫是一张 $n$ 个点 $m$ 条边的**无向图**，你可以**瞬间**在两个中间**存在路径**的点间互相移动。

现在拆除所有炸弹已经来不及了，你只能拆除了**当前位置**的炸弹，并查探到了**每个炸弹的引爆时间**。

**如果鸭科夫中的一个点被炸毁了，那么任意一端是它的所有边也会同时被炸毁。**

你必须在**能走的路被炸完之前**，赶往**唯一的出口**并离开鸭科夫，找到 $SCUTkk$ 并将它绳之以法。

现在你希望知道，**最晚**在多少秒后出发，才能保证自己可以及时从出口离开鸭科夫。

输入描述:

第一行五个整数：鸭科夫的点数  () ，鸭科夫的边数  () ，放置了定时炸弹的点数  () ，你的初始位置  ，鸭科夫唯一的终点  ()。

接下来  行，每行两个整数  () 和  ()，表示现在点  上有一个会在  秒后引爆的定时炸弹。

接下来  行，每行两个整数  和 ，表示对你来说鸭科夫中存在一条从  和  间的**无向边**。

**保证初始时至少存在一条  和  间的路径，且点  上一定存在炸弹, 点  上一定不存在炸弹。**

输出描述:

一行一个整数：**最晚**在多少秒后出发，才能保证成功从出口离开鸭科夫。

**注意：当且仅当某时刻存在连接初始位置和出口的路径，且出口未被炸毁，你才能在这一时刻离开鸭科夫。**

示例1

输入

复制

输出

复制