首先用一波神奇的操作，平面图边数m<=3*n-6，直接把m降到n，
然后对于冲突的边一条环内，一条环外，可以用并查集或者2Sat做，
当然并查集是无向的，2Sat是有向的，显然用并查集比较好 复杂度大概是O(T*n*n)
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define pb push_back
#define pii pair<int,int>
#define ft first
#define sc second
#define MAXN 200000+10
using namespace std;
int n,m;
int b[MAXN],d[MAXN],f[MAXN];
pii E[MAXN];
int find(int x){return (f[x]==x?x:f[x]=find(f[x]));}
void init_find(){
for(int i=;i<=(m<<);i++)f[i]=i;
}
void lik(int x,int y){
x=find(x),y=find(y);
if(x!=y)f[x]=y;
}
int solve(){
scanf("%d%d",&n,&m);
init_find();
for(int i=;i<=m;i++)scanf("%d%d",&E[i].ft,&E[i].sc);
int t;
for(int i=;i<=n;i++)scanf("%d",&t),d[t]=i;
if(m>*n-)return ;
memset(b,,sizeof(b));
for(int i=;i<=m;i++){
E[i].ft=d[E[i].ft],E[i].sc=d[E[i].sc];
if(E[i].ft>E[i].sc){swap(E[i].ft,E[i].sc);}
if(E[i].sc-E[i].ft==||E[i].sc-E[i].ft==n-)b[i]=;
}
pii x,y;
for(int i=;i<=m;i++){
if(b[i])continue;
for(int j=i+;j<=m;j++){
if(b[j])continue;
x=E[i],y=E[j];
if(x.ft==y.ft||x.ft==y.sc)continue;
if(x.sc==y.ft||x.sc==y.sc)continue;
if(x.ft==x.sc||y.ft==y.sc)continue;
if(x.ft>y.ft)swap(x,y);
if(y.ft<x.sc&&x.sc<y.sc){
if(find(i)==find(j))return ;
lik(i,j+m),lik(j,i+m);
}
}
}
return ;
}
int main()
{
// freopen("data.in","r",stdin);
int T;
scanf("%d",&T);
while(T--){
if(solve())printf("YES\n");
else printf("NO\n");
}
return ;
}
并查集
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define pb push_back
#define pii pair<int,int>
#define ft first
#define sc second
#define MAXN 200000+10
using namespace std;
struct TSat{
int n;
int fst[MAXN],nxt[MAXN],to[MAXN];
int cnt;
void add(int x,int y){
nxt[++cnt]=fst[x],fst[x]=cnt,to[cnt]=y;
}
void ins(int x,int y){
add(x,y+n);
add(x+n,y);
}
int dfn[MAXN],low[MAXN];
int cmp[MAXN],sta[MAXN],vis[MAXN],top;
int time_dex,tmp;
void init(int n){
this->n=n;
time_dex=tmp=cnt=top=;
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(vis,,sizeof(vis));
memset(fst,,sizeof(fst));
memset(nxt,,sizeof(nxt));
memset(to,,sizeof(to));
memset(cmp,,sizeof(cmp));
}
void Tarjan(int x){
dfn[x]=low[x]=++time_dex;
sta[++top]=x;
vis[x]=;
for(int e=fst[x];e;e=nxt[e]){
int &y=to[e];
if(!dfn[y]){
Tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(vis[y]){
low[x]=min(low[x],dfn[y]);
}
}
if(low[x]==dfn[x]){
tmp++;
while(sta[top+]!=x){
cmp[sta[top]]=tmp;
vis[sta[top]]=;
top--;
}
}
}
bool check(){
for(int i=;i<=(n<<);i++){
if(!dfn[i])Tarjan(i);
}
for(int i=;i<=n;i++){
if(cmp[i]==cmp[i+n])
return ;
}
return ;
}
}TS;
int n,m;
int b[MAXN],d[MAXN];
pii E[MAXN];
int solve(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)scanf("%d%d",&E[i].ft,&E[i].sc);
int t;
for(int i=;i<=n;i++)scanf("%d",&t),d[t]=i;
if(m>*n-)return ;
TS.init(m);
memset(b,,sizeof(b));
for(int i=;i<=m;i++){
E[i].ft=d[E[i].ft],E[i].sc=d[E[i].sc];
if(E[i].ft>E[i].sc){swap(E[i].ft,E[i].sc);}
if(E[i].sc-E[i].ft==||E[i].sc-E[i].ft==n-)b[i]=;
}
pii x,y;
for(int i=;i<=m;i++){
if(b[i])continue;
for(int j=i+;j<=m;j++){
if(b[j])continue;
x=E[i],y=E[j];
if(x.ft==y.ft||x.ft==y.sc)continue;
if(x.sc==y.ft||x.sc==y.sc)continue;
if(x.ft==x.sc||y.ft==y.sc)continue;
if(x.ft>y.ft)swap(x,y);
if(y.ft<x.sc&&x.sc<y.sc){
TS.ins(i,j);
TS.ins(j,i);
}
}
}
return TS.check();
}
int main()
{
// freopen("data.in","r",stdin);
int T;
scanf("%d",&T);
while(T--){
if(solve())printf("YES\n");
else printf("NO\n");
}
return ;
}
2Sat