BZOJ 1997 [Hnoi2010] Planar

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<time.h>
#include<vector>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#define LL long long
#define pii pair<int,int>
using namespace std;
const int N=3000000;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;

int T,n,m,E,tim,sccn;
int pos[10000],fir[10000],nex[N],arr[N];
int dfn[10000],scc[10000],low[10000];
pii a[10010];
stack<int> S;

namespace FastIO {
	template<typename tp> inline void read(tp &x) {
		x=0; register char c=getchar(); register bool f=0;
		for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
		for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
		if(f) x=-x;
	}
	template<typename tp> inline void write(tp x) {
		if (x==0) return (void) (putchar('0'));
   	if (x<0) putchar('-'),x=-x;
   	int pr[20]; register int cnt=0;
   	for (;x;x/=10) pr[++cnt]=x%10;
   	while (cnt) putchar(pr[cnt--]+'0');
	}
	template<typename tp> inline void writeln(tp x) {
		write(x);
		putchar('\n');
	}
}
using namespace FastIO;

inline void Add_Edge(int x,int y) {
	nex[++E]=fir[x];
	fir[x]=E;
	arr[E]=y;
}

inline int Check(int x,int y) {
	if (a[y].first<a[x].first) {
		if (a[y].second>a[x].first&&a[y].second<a[x].second) return 1;
		else return 0;
	}
	if (a[y].second>a[x].second) {
		if (a[y].first>a[x].first&&a[y].first<a[x].second) return 1;
		else return 0;
	}
	return 0;
}

void dfs(int x) {
	dfn[x]=low[x]=++tim;
	S.push(x);
	for (int i=fir[x];i;i=nex[i]) {
		int v=arr[i];
		if (!dfn[v]) {
			dfs(v);
			low[x]=min(low[x],low[v]);
		}
		else if (!scc[v]) low[x]=min(low[x],dfn[v]);
	}
	if (dfn[x]==low[x]) {
		++sccn;
		while (1) {
			int v=S.top(); S.pop();
			scc[v]=sccn;
			if (x==v) break;
		}
	}
}

int Two_SAT() {
	memset(dfn,0,sizeof(int)*(m*2+10));
	memset(low,0,sizeof(int)*(m*2+10));
	for (int i=2;i<=m*2+1;i++)
		if (!dfn[i]) dfs(i);
	for (int i=2;i<=m*2+1;i++)
		if (scc[i]==scc[i^1]) return 0;
	return 1;
}

void Solve() {
	read(n); read(m);
	memset(pos,0,sizeof(int)*(n+1));
	for (int i=1;i<=m;i++) {
		int u,v;
		read(u); read(v);
		a[i]=make_pair(u,v);
	}
	for (int i=1;i<=n;i++) {
		int x; read(x); pos[x]=i;
	}
	if (m>n*3-6) return (void) puts("NO");
	for (int i=1;i<=m;i++) {
		a[i].first=pos[a[i].first];
		a[i].second=pos[a[i].second];
		if (a[i].first>a[i].second) swap(a[i].first,a[i].second);
	}
	E=0;
	memset(fir,0,sizeof(int)*(m*2+10));
	memset(scc,0,sizeof(int)*(m*2+10));
	for (int i=1;i<=m;i++) {
		for (int j=i+1;j<=m;j++) {
			if (Check(i,j)) {
				Add_Edge(i*2,j*2+1);	Add_Edge(i*2+1,j*2);
				Add_Edge(j*2,i*2+1);	Add_Edge(j*2+1,i*2);
			}
		}
	}
	if (Two_SAT()) puts("YES");
	else puts("NO");
}

int main() {
	read(T);
	while (T--) Solve();
	return 0;
}