题目传送门

分析

首先一张图是平面图的必要条件为 \(m\leq 3*n-6\)，

然后考虑到这题的图存在哈密尔顿回路，也就是说非环边因为跨立形成奇环即为无解

那么直接拆点跑2-SAT就可以了

代码

#include 
#include 
#define rr register
using namespace std;
const int N=1211; struct node{int y,next;}e[N*N];
int dfn[N],low[N],v[N],stac[N],col[N],rk[N],as[N];
int et,flag,tot,Top,cnt,n,m,X[N*10],Y[N*10];
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans;
}
inline signed min(int a,int b){return a3*n-6) {puts("NO"); continue;}
		for (rr int i=1;i<=m;++i){
			X[i]=rk[X[i]],Y[i]=rk[Y[i]];
			if (X[i]>Y[i]) X[i]^=Y[i],Y[i]^=X[i],X[i]^=Y[i];
			if (X[i]+1==Y[i]||(X[i]==1&&Y[i]==n)) v[i]=1;
		}
		for (rr int i=1;i