记录编号	261759	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]地牢里的背叛	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.418 s
提交时间	2016-05-18 16:23:17	内存使用	37.59 MiB

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 200010
using namespace std;
inline void in(int&x){for(x=getchar();x<48|x>57;x=getchar());x^=48;for(int tmp=getchar();47<tmp&tmp<58;tmp=getchar())x=(x<<1)+(x<<3)+(tmp^48);}
int n,m,Q,num,cnt,ti;
int sn[maxn],fa[maxn][20],sta[maxn],bn[maxn][2],c1[maxn],c2[maxn],bg[maxn],Rt[maxn],dfn[maxn],low[maxn];
bool fg=1,vis[maxn],ins[maxn];
int shu=1,first[maxn];
struct edge{int u,v,nx;}o[maxn<<1],st[maxn<<1];
inline void add(int u,int v){o[++shu].u=u,o[shu].v=v,o[shu].nx=first[u],first[u]=shu;}
inline void tarjan(int x,int f){
	low[x]=dfn[x]=++num;
	sta[++sta[0]]=x,ins[x]=1;
	for(int i=first[x];i;i=o[i].nx){
		if(i==(f^1))continue;
		if(!dfn[o[i].v]){
			tarjan(o[i].v,i);
			low[x]=min(low[x],low[o[i].v]);
		}else if(ins[o[i].v])low[x]=min(low[x],dfn[o[i].v]);
	}
	if(low[x]==dfn[x]){
		int now;++cnt;
		do{
			now=sta[sta[0]--];
			ins[now]=0,bg[now]=cnt;
		}while(now!=x);
	}
}
inline void dfs(int x,int f,int rt,int dep){
	sn[x]=dep,Rt[x]=rt;
	fa[x][0]=f;
	vis[x]=1;
	for(int i=1;(1<<i)<=sn[x];++i)fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int i=first[x];i;i=o[i].nx){
		if(o[i].v==f||vis[o[i].v])continue;
		dfs(o[i].v,x,rt,dep+1);
	}
}
inline int LCA(int x,int y){
	if(sn[x]<sn[y])swap(x,y);
	for(int i=19;~i;--i)if(sn[fa[x][i]]>=sn[y])x=fa[x][i];
	if(x==y)return x;
	for(int i=19;~i;--i)if(sn[fa[x][i]]!=sn[fa[y][i]])x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
inline void dfs1(int x,int f){
	++ti,vis[x]=1;
	for(int i=first[x];i;i=o[i].nx){
		if(o[i].v==f||vis[o[i].v])continue;
		dfs1(o[i].v,x);
		c1[x]+=c1[o[i].v],c2[x]+=c2[o[i].v];
	}
	if(x&&c1[x]>0&&c2[x]>0)fg=0;
}
int main(){
	freopen("MM.in","r",stdin);
	freopen("MM.out","w",stdout);
	in(n),in(m),in(Q);
	for(int i=1,u,v;i<=m;++i)in(u),in(v),add(u,v),add(v,u);
	for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i,0);
	for(int i=1;i<=Q;++i)in(bn[i][0]),in(bn[i][1]);
	memcpy(st,o,sizeof(o));
	int shu1=shu;shu=0;
	memset(first,0,sizeof(first));
	for(int i=1;i<=shu1;++i)if(bg[st[i].u]!=bg[st[i].v])add(bg[st[i].u],bg[st[i].v]);
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=cnt;++i)if(!vis[i])dfs(i,i,i,1);
	for(int i=1;i<=Q;++i){
		if(Rt[bg[bn[i][0]]]!=Rt[bg[bn[i][1]]]){
			fg=0;break;
		}
		int x=bg[bn[i][0]],y=bg[bn[i][1]];
		if(x==y)continue;
		int lca=LCA(x,y);
		++c1[x],--c1[lca];
		++c2[y],--c2[lca];
	}
	if(fg){
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=cnt;++i)if(!vis[Rt[i]])dfs1(Rt[i],Rt[i]);
	}
	if(!fg)puts("No");
	else puts("Yes");
	//while(1);
}