Skip to content

1452: If only

题目

题目描述

有一个玩家在一张无向图上玩游戏,玩家现在在 $s$ 号点,他希望在 $k$ 秒后恰好移动到 $t$ 号点。玩家每秒必须移动到相邻的结点上。

你需要判断:如果玩家采取最优策略,是否能达成目标。

如果玩家某时刻无法移动,亦视为任务失败。

Input

请从 stdin 读入。

输入第一行为五个正整数,$n, m, s, t, k ~ (2 \leq n \leq 10 ^ 5, 1 \leq m \leq 10 ^ 5, k \leq 10 ^ 9, 1 \leq s, t \leq n, s \neq t)$。

接下来 $m$ 行,第 $i$ 行有两个正整数 $u_i, v_i (1 \leq u_i, v_i \leq n)$,表示图上有一条 $u_i$ 到 $v_i$ 的边。

存在自环时,一个点与自己相邻。

对于 $30$ 分的数据,$n, m, k \leq 1000$。

Output

请输出到 stdout 中。

输出一行一个字符串,Yes 或者 No,表示你的答案。

Sample Input

2 1 1 2 999999999 1 2

2 1 1 2 2 1 2 5 5 1 5 3 1 1 1 2 2 3 3 4 4 5

5 5 1 5 5 1 1 1 2 2 3 3 4 4 5

Sample Output

Yes No No Yes

Constraints

Time Limit: 0.25s

Memory Limit: 512MB

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!