You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一个 $n$ 个节点，$m$ 条边的有向无环连通图，其中有 $k$ 个点是关键点。问图上是否存在一条简单路径，使得所有关键点都在路径上。

点从 $1$ 开始编号。

输入格式

本题多测。

对于每个测试点，第一行一个整数 $T$，表示数据组数。

接下来有 $T$ 组数据，每组数据格式如下：

第一行三个整数 $n,m$，分别表示图的点数，边数以及关键点个数。

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

接下来一行一个整数 $k$。

接下来一行 $k$ 个整数 $q_1,q_2,...,q_k$，表示这 $k$ 个关键点的标号。

输出格式

一行字符串，如果存在满足条件的路径就输出 Yes，否则输出 No。

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

Yes

样例解释

6->4->2->7 即为一条合法的路径。

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

No

样例解释

显然不存在任何一条路径能同时经过 2,4,5 三点。

数据范围

本题开启捆绑测试。

对于 $100\%$ 的数据，保证：$1\le \sum n,\sum m\le 10^6$，$0\le k\le n$，且图是一个有向无环图。保证 $q_i$ 互不相同。