题目描述

若能将无向图 $G=(V, E)$ 画在平面上使得任意两条无重合顶点的边不相交，则称 $G$ 是平面图。判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要判定的是一类特殊的图，图中存在一个包含所有顶点的环，即存在哈密顿回路。

输入格式

输入文件的第一行是一个正整数 $T$，表示数据组数 (每组数据描述一个需要判定的图)。接下来从输入文件第二行开始有 $T$ 组数据，每组数据的第一行是用空格隔开的两个正整数 $N$ 和 $M$，分别表示对应图的顶点数和边数。紧接着的 $M$ 行，每行是用空格隔开的两个正整数 $u$ 和 $v$ $\left(1\leq u,v\leq N\right)$，表示对应图的一条边 $\left(u,v\right)$, 输入的数据保证所有边仅出现一次。每组数据的最后一行是用空格隔开的 $N$ 个正整数，从左到右表示对应图中的一个哈密顿回路：$V_1,V_2,…,V_N$，即对任意 $i\not=j$ 有 $V_i\not=V_j$ 且对任意 $1\leq i\leq N-1$ 有 $\left(V_i,V_i-1\right)\in E$ 及 $\left(V_1,V_N\right)\in E$。输入的数据保证 $100\%$ 的数据满足 $T\leq100,3\leq N\leq200,M\leq10000$。

输出格式

包含 $T$ 行，若输入文件的第 $i$ 组数据所对应图是平面图，则在第 $i$ 行输出 $\text{YES}$，否则在第 $i$ 行输出 $\text{NO}$，注意均为大写字母

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

NO
YES

提示

感谢@hibiki 对题目进行修正

感谢@@Anguei 提供latex题面