记录编号	390678	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]地牢里的背叛	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.836 s
提交时间	2017-04-03 17:58:27	内存使用	55.62 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e6+10;
int n,m,q,w[N],next[N],head[N];
bool vis[N];
void add(int f,int t){
	static int cnt=1;
	w[++cnt]=t;
	next[cnt]=head[f];
	head[f]=cnt;
}
int S[N],fa[N];
int find(int x){return S[x]==x?x:S[x]=find(S[x]);}
void dfs(int x){
	for (int i=head[x];i;i=next[i])
	if (!vis[i]){
		vis[i]=vis[i^1]=1;
		if (fa[w[i]]){
			for (int y=x;;){
				int v=find(y);y=fa[v];
				if (v==find(w[i])) break;
				S[v]=find(w[i]);
			}
		}
		else fa[w[i]]=x,dfs(w[i]);
	}
}
vector<int> E[N];
//tag为标记,即将区间置为某个值,v为这条边的值,-1:向下;1:向上 
int son[N][2],v[N],tag[N],id;
bool root[N],ise[N],rev[N],isdown[N],isup[N];
void visit(int x){
	root[x]=1;
	for (int i=E[x].size()-1;i>=0;i--){
		int v=E[x][i];
		if (!fa[v]){
			fa[fa[v]=++id]=x;
			root[id]=ise[id]=1;
			visit(v);
		}
	}
}
#define lc son[x][0]
#define rc son[x][1]
void update(int x){
	isup[x]=isdown[x]=0;
	if (lc) isdown[x]|=isdown[lc],isup[x]|=isup[lc];
	if (rc) isdown[x]|=isdown[rc],isup[x]|=isup[rc];
	if (v[x]>0) isup[x]=1;
	if (v[x]<0) isdown[x]=1;
}
void flip(int x){
	swap(lc,rc);
	swap(isdown[x],isup[x]);
	v[x]=-v[x];
	tag[x]=-tag[x];
	rev[x]^=1;
}
void paint(int x,int C){
	if (ise[x]) v[x]=C;
	tag[x]=C;
	C>0?isup[x]=1:isdown[x]=1;
}
void pushdown(int x){
	if (!x) return;
	if (rev[x]){
		if (lc) flip(lc);
		if (rc) flip(rc);
		rev[x]=0;
	}
	if (tag[x]){
		if (lc) paint(lc,tag[x]);
		if (rc) paint(rc,tag[x]);
		tag[x]=0;
	}
}
void rot(int x){
	int y=fa[x],z=fa[y];
	bool b=(x==son[y][1]);
	fa[son[y][b]=son[x][!b]]=y;
	fa[son[x][!b]=y]=x;
	fa[x]=z;
	if (y==son[z][0]) son[z][0]=x;else
	if (y==son[z][1]) son[z][1]=x;
	root[x]=root[y];root[y]=0;
	update(y);update(x);
}
void splay(int x){
	pushdown(x);
	for (;!root[x];rot(x)){
		int y=fa[x],z=fa[y];
		pushdown(z);pushdown(y);pushdown(x);
		if (root[y]) continue;
		rot((x==son[y][0])==(y==son[z][0])?y:x);
	}
}
void access(int x){
	splay(x);
	root[rc]=1;rc=0;
	update(x);
	while (fa[x]){
		int y=fa[x];
		splay(y);
		root[son[y][1]]=1;
		root[son[y][1]=x]=0;
		update(y);
		splay(x);
	}
}
int link[N];
int getset(int x){return link[x]==x?x:link[x]=getset(link[x]);}
int main()
{
	freopen("MM.in","r",stdin);
	freopen("MM.out","w",stdout);
	scanf("%d%d%d",&n,&m,&q);
	for (int i=1;i<=n;i++) S[i]=link[i]=i;
	for (int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
		link[getset(x)]=getset(y);
	}
	for (int i=1;i<=n;i++)
		if (!fa[i]) fa[i]=i,dfs(i);
	for (int i=1;i<=n;i++)
	for (int j=head[i];j;j=next[j]){
		int S=find(i),T=find(w[j]);
		if (S!=T){
			E[S].push_back(T);
			E[T].push_back(S);
		}
	}
	for (int i=1;i<=n;i++) fa[i]=0;id=n;
	for (int i=1;i<=n;i++)
		if (!fa[i]) fa[i]=i,visit(i),fa[i]=0;
	while (q--){
		int x,y;
		scanf("%d%d",&x,&y);
		if (getset(x)!=getset(y)) puts("No"),exit(0);
		x=find(x);y=find(y);
		if (x==y) continue;
		access(x);
		flip(x);
		access(y);
		if (isup[y]) puts("No"),exit(0);
		paint(y,-1);
	}
	puts("Yes");
	return 0;
}