[HNOI2010] 平面图判定

题号：NC239232
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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

输入描述:

输入文件的第一行是一个正整数 ，表示数据组数 (每组数据描述一个需要判定的图)。

接下来从输入文件第二行开始有  组数据，每组数据的第一行是用空格隔开的两个正整数  和 ，分别表示对应图的顶点数和边数。

紧接着的  行，每行是用空格隔开的两个正整数  和  ，表示对应图的一条边 , 输入的数据保证所有边仅出现一次。

每组数据的最后一行是用空格隔开的  个正整数，从左到右表示对应图中的一个哈密顿回路：，即对任意  有  且对任意  有  及 。

输入的数据保证  的数据满足 。

输出描述:

包含  行，若输入文件的第  组数据所对应图是平面图，则在第  行输出 ，否则在第  行输出 ，注意均为大写字母

示例1

输入

复制

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