题目描述

若能将无向图 $G=(V,E)$ 画在平面上使得任意两条无重合顶点的边不相交，则称 $G$ 是平面图。

判定一个图是否为平面图的问题是图论中的一个重要问题。

现在假设你要判定的是一类特殊的图，图中存在一个包含所有顶点的环，即存在哈密顿回路。

请你判定它们是否是平面图。

输入格式

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

每组测试数据第一行包含两个整数 $N$和 $M$，分别表示对应图的顶点数和边数。

之后 $M$行，每行包含两个整数$u$和 $v$，表示对应图的一条边 $(u,v)$，输入数据保证所有边仅出现一次。

最后一行，包含 $N$ 个整数，从左到右表示对应图中的一个哈密顿回路。

输出格式

输出共 $T$ 行。

如果第 $i$组数据对应的图是平面图，则第$i$行输出 YES，否则输出 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

数据范围

$T≤100,3≤N≤200,M≤10000$

来源

• BZOJ1997
• 算法竞赛进阶指南