定位：2-SAT。
前置知识
平面图
平面图：存在一种或几种方法，将这个图画在平面上，除了点之外，所有边之间没有交点的图。
例如，下面这两个都是平面图，因为前一个图可以拉成后一个的样子：
平面图定理
连通平面图有几个常用的定理：
记一个连通平面图的点数为 ，边数为 。
- 当 时，有 。
- 当 时，存在一个点的度数不小于 。
定义一个连通平面图把平面分成的块数为 。如上面这个平面图，（算上了最外圈以外的无限大的平面部分）。有：。
平面图有关的更多笔记都会在以后写上。这里先写个大概。
题解
算法
题目简述：
给定一个无向图，保证存在一条哈密顿回路。判定是否是平面图。。
存在一条哈密顿回路，不妨把这个回路当成一个圆，然后考虑其他的边。
现在我们的圆已经搞出来了，问题就是圆里面的各种弦有很多的相交。这并不代表圆里面有弦就不是平面图了，因为我们可以把一些边拉在外面。这里相比都能看出把 拉到圆外面去，从圆周外绕过来，这就是个完美的平面图了，但是重要的是怎么让电脑知道要这么拉。
想到如果可以把所有有交点的弦提出来，那么这两个弦是不可能都在圆里了，如果一个在圆外一个在圆里显然可以，两个都在圆外，手玩一下就发现不行。因此就是：弦 拉到圆外或弦 拉到圆外。转化成 2-SAT 问题的解的存在性判定，迎刃而解。
题目的边数很大，不能直接枚举每条边，但是考虑到平面图的性质，因为 ，所以 ，如果大于这个，就一定不是平面图。提前判掉之后， 就是 以内了。可以枚举两个相交的弦，然后跑 2-SAT。
如何判定两个弦相交呢？考虑到在一个环上，按照环的顺序顺时针（或逆时针）编号，如果一个圆按顺序放了 ，一个弦连接到 ，一个弦连接到 ，就一定在内侧相交。为什么？左转插头 DP 找证明即可。
至此这道题就做完了。代码如下：
代码
#include<bits/stdc++.h>
using namespace std;
const int max_n=20005,max_m=2000006;
inline int read(){
int x=0;bool w=0;char c=getchar();
while(c<'0' || c>'9') w|=c=='-',c=getchar();
while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return w?-x:x;
}
struct graph{
int ct,hd[max_n],to[max_m],nx[max_m];
graph(){ct=1;}
inline void clear(){
ct=1;
memset(hd,0,sizeof(hd));
}
inline void add(int u,int v){
nx[++ct]=hd[u],hd[u]=ct,to[ct]=v;
}
}e;
int n,m,a[max_n],b[max_n];
stack<int> s;
bool in[max_n];
int cntdfn,tot,dfn[max_n],low[max_n],col[max_n];
inline void Tarjan(int u,int fa){ // 2-SAT
s.push(u),in[u]=1;
dfn[u]=low[u]=++cntdfn;
for(register int i=e.hd[u];i;i=e.nx[i]){
int v=e.to[i];
if(!dfn[v]){
Tarjan(v,u);
low[u]=min(low[u],low[v]);
}
else if(in[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
int v=u;
++tot;
do{
v=s.top();s.pop();
in[v]=0,
col[v]=tot;
}while(v!=u);
}
}
struct edge{
int u,v;
edge(){u=v=0;}
inline void init(int x,int y){
u=x,v=y;
}
}q[max_n];
#define opp(x) (x+m)
int cntid;
bool mp[max_n][max_n];
signed main(){
int T=read();
while(T--){
n=read(),m=read();
if(m>3*n-6){
int x,y;
for(register int i=1;i<=m;++i)
x=read(),y=read();
for(register int i=1;i<=n;++i)
x=read();
x+=y;
puts("NO");
continue;
}
cntdfn=cntid=tot=0;
e.clear();
while(!s.empty()) s.pop();
memset(dfn,0,sizeof(dfn)),
memset(low,0,sizeof(low)),
memset(col,0,sizeof(col));
for(register int i=1;i<=m;++i){
int u=read(),v=read();
mp[u][v]=mp[v][u]=1;
}
for(register int i=1;i<=n;++i){
a[i]=read();
b[a[i]]=i;
if(i>=2)
mp[a[i]][a[i-1]]=mp[a[i-1]][a[i]]=0;
if(i==n)
mp[a[1]][a[n]]=mp[a[n]][a[1]]=0;
} // 过滤在圆上的边，得到弦
for(register int i=2;i<=n;++i)
for(register int j=1;j<i;++j)
if(mp[i][j]){
q[++cntid].init(i,j);
mp[i][j]=mp[j][i]=0;
}
m=cntid;
for(register int i=2;i<=m;++i)
for(register int j=1;j<i;++j){
int u=b[q[i].u],v=b[q[i].v];
int x=b[q[j].u],y=b[q[j].v];
if(u>v) swap(u,v);
if(x>y) swap(x,y);
if((u<x && v>x && v<y) || (v>y && u>x && u<y)){
e.add(i,opp(j)),
e.add(opp(i),j),
e.add(j,opp(i)),
e.add(opp(j),i);
}// 一个在外一个在内
}
for(register int i=1;i<=m*2;++i)
if(!dfn[i])
Tarjan(i,i);
bool ok=1;
for(register int i=1;i<=m && ok;++i)
if(col[i]==col[opp(i)])
ok=0;
puts(ok?"YES":"NO");
}
return 0;
}
