3323. [HNOI 2010]平面图判定

【题目描述】

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

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

【输入格式】

输入文件第一行是一个正整数$ T $，表示数据组数（每组数据描述一个要判定的图）。接下来从输入文件第二行开始有$ T $组数据，每组数据的第一行是用空格隔开的两个正整数$ N $和$ M $，分别表示对应图的顶点数和边数。紧接着的$ M $行，每行是用空格隔开的两个正整数$ u $和$ v (1 ≤ u, v ≤ N ) $，表示对应图的一条边$ (u, v) $，输入的数据保证所有边仅出现一次。

每组数据的最后一行是用空格隔开的N个正整数，从左到右表示对应图中的一个哈密顿回路：$ V_1 ,V_2 ... V_N $，即对任意$ i≠j $有$ V_i ≠V_j $且对任意$ 1 ≤ i ≤ N - 1 $有$ (V_i ,V_{i+1} )∈E $及$ (V_1 ,V_N )∈E $。输入的数据保证$ 100\% $的数据满足$ T ≤ 100, 3 ≤ N ≤ 200 , M ≤ 10000 $

【输出格式】

输出文件包含$ T $行，若输入文件的第$ i $组数据所对应图是平面图，则在第$ i $行输出'$ YES $'，否则在第$ i $行输出'$ 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