1001. 让路径生存吧！

题目描述

给定一张包含 $n$ 个点和 $m$ 条边的有向图。你位于 $1$ 号点，目标位于 $n$ 号点。

接下来依次发生 $q$ 次操作。第 $i$ 次操作会永久删除所有从点 $p_i$ 出发的边。

你需要求出最大的操作次数 $k$，使得执行完前 $k$ 次操作后，仍然存在一条从点 $1$ 到点 $n$ 的路径。

• 如果初始时就不存在从点 $1$ 到点 $n$ 的路径，输出 NO。
• 如果执行完全部 $q$ 次操作后仍然存在路径，输出 YES。
• 否则，输出满足条件的最大整数 $k$。特别地，答案可能为 $0$。

输入格式

第一行包含一个整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行包含三个整数 $n,m,q$，分别表示点数、边数和操作次数。

接下来 $m$ 行，每行包含两个整数 $u_i,v_i$，表示存在一条从点 $u_i$ 指向点 $v_i$ 的有向边。

接下来一行包含 $q$ 个整数 $p_1,p_2,\ldots,p_q$。第 $i$ 次操作会删除所有从点 $p_i$ 出发的边。

对于唯一一组测试数据，保证：

$T=10^4$； $3\le n\le 10^5$； $1\le m\le 10^6$； $1\le q\le n-2$； $1\le u_i,v_i\le n$； $1<p_i<n$； $\sum n=10^6$； $\sum m=5\times 10^6$。

对于每组测试数据，保证 $p_1,p_2,\ldots,p_q$ 两两不同，且所有有向边两两不同。

输出格式

对于每组测试数据输出一行：

• 初始时不存在从点 $1$ 到点 $n$ 的路径，输出 NO；
• 全部操作结束后仍然存在路径，输出 YES；
• 否则输出满足条件的最大整数 $k$。

样例输入

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

样例输出

1
NO

来源：2026杭电多校-测试专用（肖岱恩） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1236&pid=1001