题目描述
在一款虚拟游戏中,共有 n 个区域,有 m 条单向通行的隧道连接两个区域。你的对手是一个特殊 BOSS。
BOSS 可以释放 k 次炸弹,第 i 次可以摧毁以编号为 pi 的区域为起点的所有隧道。
你的技能是 Haste,每次使用可以迅速通过你所在的区域到 BOSS 所在区域的最短路径并对 BOSS 进行攻击。由于你可以掌控虚拟空间,你的每次攻击都可以对 BOSS 造成致命伤害。
初始时你在 1 号区域,BOSS 在第 n 号区域。你想知道,在保证击败 BOSS 的情况下,你最晚要在 BOSS 第几次释放炸弹后使用 Haste 技能?
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行,每行两个整数 xi,yi,表示存在一条以 xi 为起点,yi 为终点的单向隧道。
接下来一行 k 个整数 pi,表示 BOSS 第 i 次释放炸弹时的攻击起点。
输出格式
输出分为以下 4 种:
- 若你在 BOSS 首次释放炸弹前无法击败 BOSS,输出 NO 。
- 若你在 BOSS 最后一次释放炸弹后仍能击败 Wrath,输出 YES 。
- 若你仅能在 BOSS 首次释放炸弹前击败 BOSS,输出 0 。
- 其他情况下,输出一个整数,表示答案。
样例输入输出
说明/提示
对于 100% 的数据, 2≤n≤105 , 1≤m≤106 , 1≤k≤n−2 , 1≤xi,yi≤n, 1<pi<n ;
保证对于任意 1≤i,j≤k ,都有 pi=pj 。保证对于任意 1≤i,j≤m ,都有 xi=xj 或 yi=yj 。
测试点编号 |
n≤ |
m≤ |
k≤ |
特殊性质 |
1∼6 |
2000 |
104 |
2000 |
无 |
7∼8 |
5000 |
5×104 |
5000 |
保证输入数据构成 DAG,数据随机 |
9 |
105 |
105 |
保证输入数据构成链 |
10 |
保证输入数据构成 n 元环 |
11∼12 |
106 |
500 |
数据随机 |
12∼20 |
105 |
无 |