P3209 [HNOI2010] Planarity Testing

If an undirected graph $G=(V, E)$ can be drawn in the plane such that any two edges that do not share an endpoint do not intersect, then $G$ is called a planar graph. Deciding whether a graph is planar is an important problem in graph theory. Now suppose you are to decide this for a special class of graphs that contain a cycle passing through all vertices, i.e., there exists a Hamiltonian cycle.

The first line of the input file contains a positive integer $T$, indicating the number of test cases (each test case describes one graph to be decided). Starting from the second line, there are $T$ test cases. For each test case, the first line contains two positive integers $N$ and $M$ separated by a space, representing the number of vertices and the number of edges of the corresponding graph, respectively. The next $M$ lines each contain two positive integers $u$ and $v$ $\left(1\leq u,v\leq N\right)$ separated by a space, representing an edge $\left(u,v\right)$ of the graph. The input guarantees that each edge appears exactly once. The last line of each test case contains $N$ integers, from left to right representing a Hamiltonian cycle of the corresponding graph: $V_1,V_2,\dots,V_N$, i.e., for any $i\not=j$ we have $V_i\not=V_j$, and for any $1\leq i\leq N-1$ we have $\left(V_i,V_{i+1}\right)\in E$ and $\left(V_1,V_N\right)\in E$. The input guarantees that $100\%$ of the testdata satisfy $T\leq 100$, $3\leq N\leq 200$, $M\leq 10000$.

Output $T$ lines. If the graph in the $i$-th test case is planar, print `YES` on the $i$-th line; otherwise, print `NO`. Note that they must be uppercase letters.

Thanks to @hibiki for correcting the problem. Thanks to @Anguei for providing the LaTeX problem statement. Translated by ChatGPT 5