Skip to content

1453: Only if

题目

题目描述

有 $p$ 个玩家在一张无向图上玩游戏,$i$ 号玩家现在在 $s_i$ 号点。每个玩家希望在 $k$ 秒后恰好移动到 ${t_1, t_2, \cdots, t_p}$ 中的一个点上。每个玩家每秒开始时必须移动到相邻的点上,并且两个玩家不能在移动后处在同一个点上。

你需要判断:如果玩家们合作并且采取最优策略,是否能让所有玩家达成目标。

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

Input

请从 stdin 读入。

输入第一行为五个正整数,$n, m, p, k ~ (1 \leq p \leq n, m \leq 100, 1 \leq k \leq 100)$。

接下来一行 $p$ 个正整数,第 $i$ 个为 $s_i (1\leq s_i\leq n)$。

接下来一行 $p$ 个正整数,第 $i$ 个为 $t_i (1\leq t_i\leq n)$。

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

输入保证,${s_1, \cdots, s_p, t_1, \cdots, t_p}$ 互不相同。存在自环时,一个点与自己相邻。

Output

请输出到 stdout 中。

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

Sample Input

7 6 2 4 1 3 4 5 1 2 2 3 3 6 2 4 2 5 4 7

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

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

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

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

Sample Output

Yes

Yes

Yes

No

Note

对于样例 $1$,图长这样: 4 - 7 | 1 - 2 - 3 - 6 | 5

一种可能的移动轨迹是:1-2-4-7-43-6-3-2-5

对于样例 $2$,一种可能的移动轨迹是:1-2-32-3-4

对于样例 $3$,一种可能的移动轨迹是:2-3-43-2-1。仅在考虑顶点上玩家重合的情况,而无需在边上判断。

Constraints

Time Limit: 1s

Memory Limit: 512MB

Oops! 本题目还没有解答!

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

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

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