Description

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.

Input Format

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 Format

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.

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

Hint

Thanks to @hibiki for correcting the problem.

Thanks to @Anguei for providing the LaTeX problem statement.

Translated by ChatGPT 5