2-SAT。
首先有平面图定理 m<=3*n-6，如果不满足这条件肯定不是平面图，直接退出。
然后构成哈密顿回路的边直接忽略。
把哈密顿回路当成一个圆，
如果俩条边交叉（用心去感受），只能一条边在圆内，另一条在圆外。
这个是2-sat的A,B要不同时取，要不同时不取模型。
如果俩个交叉，只能一个在内，一个在外。
和A，B俩者不能同时取有区别，需要注意。
可能存在3个方案(A,B’),(B,A’),(A’,B’)。
连方案都不要，直接tarjan完就过了。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 10000 + 10;
const int maxm = 3000000 + 10; int g[maxn],v[maxm],next[maxm],eid;
int a[maxn],b[maxn],c[maxn],pos[maxn];
bool t[maxn];
int vis[maxn];
int s[maxn],sp;
int dfn[maxn],low[maxn],vid;
int color[maxn],cid;
int T,n,m; void addedge(int a,int b) {
v[eid]=b; next[eid]=g[a]; g[a]=eid++;
v[eid]=a; next[eid]=g[b]; g[b]=eid++;
} bool build() {
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d%d",&a[i],&b[i]);
for(int i=1;i<=n;i++) {
scanf("%d",&c[i]);
pos[c[i]]=i;
}
if(m>3*n-6) {
printf("NO\n");
return false;
}
memset(g,-1,sizeof(g)); eid=0;
memset(t,0,sizeof(t));
for(int i=1;i<=m;i++) {
a[i]=pos[a[i]];
b[i]=pos[b[i]];
if(a[i]>b[i]) swap(a[i],b[i]);
}
for(int i=1;i<=m;i++)
if(a[i]+1==b[i] || (a[i]==1&&b[i]==n)) t[i]=true;
for(int i=1;i<=m;i++) if(!t[i]) {
for(int j=1;j<=m;j++) if(i!=j && !t[j])
if(a[i]<a[j] && a[j]<b[i] && b[i]<b[j]) {
addedge((i<<1),(j<<1)|1);
addedge((i<<1)|1,(j<<1));
}
}
return true;
} void tarjan(int u) {
dfn[u]=low[u]=++vid;
vis[u]=1; s[++sp]=u; for(int i=g[u];~i;i=next[i]) {
if(!vis[v[i]]) {
tarjan(v[i]);
low[u]=min(low[u],low[v[i]]);
}
else if(vis[v[i]]==1)
low[u]=min(low[u],dfn[v[i]]);
} if(dfn[u]==low[u]) {
++cid;
do {
color[s[sp]]=cid;
vis[s[sp]]=2;
}while(s[sp--]!=u);
}
} void solve() {
memset(vis,0,sizeof(vis));
vid=cid=sp=0;
for(int i=1;i<=m;i++) if(!t[i]) {
if(!vis[i<<1]) tarjan(i<<1);
if(!vis[i<<1|1]) tarjan((i<<1|1));
}
for(int i=1;i<=m;i++) if(!t[i]&&color[i<<1]==color[i<<1|1]) {
printf("NO\n");
return;
}
printf("YES\n");
} int main() {
scanf("%d",&T);
while(T--) if(build()) solve();
return 0;
}