学步园

/*
分析：
    Tarjan。
    判断俩图形状是否一样，这个图比较简单，只有链和环，所以很
容易判断的，1Y、每次看到1Y都会很happy的有木有~！。

                                                  2013-06-15
*/

#include"iostream"
#include"cstdio"
#include"stack"
#include"cstring"
#include"algorithm"
using namespace std;
const int N=10005;

int n[2],m[2],cnt_line[2],cnt_cir[2],cnt_line_node[2][N],cnt_cir_node[2][N];
int LOW[N],DFN[N],instack[N],index_s,indegree[2][N];
struct Edge{
	int v,next;
}edge[2][2*N];
int tot[2],head[2][N];
void add(int k,int a,int b){
	edge[k][tot[k]].v=b;edge[k][tot[k]].next=head[k][a];head[k][a]=tot[k]++;
	edge[k][tot[k]].v=a;edge[k][tot[k]].next=head[k][b];head[k][b]=tot[k]++;
}

void build_map(int k)
{
	int a,b;
	tot[k]=0;
	memset(head[k],-1,sizeof(head[k]));
	memset(indegree[k],0,sizeof(indegree[k]));
	scanf("%d%d",&n[k],&m[k]);
	while(m[k]--)
	{
		scanf("%d%d",&a,&b);
		add(k,a,b);
		indegree[k][a]++;
		indegree[k][b]++;
	}
}

stack<int>st;
void Tarjan(int k,int s)
{
	int j,v;
	st.push(s);
	instack[s]=1;
	DFN[s]=LOW[s]=++index_s;
	for(j=head[k][s];j!=-1;j=edge[k][j].next)
	{
		v=edge[k][j].v;
		if(instack[v])	LOW[s]=LOW[s]>DFN[v]?DFN[v]:LOW[s];
		else if(DFN[v]==-1)
		{
			Tarjan(k,v);
			LOW[s]=LOW[s]>LOW[v]?LOW[v]:LOW[s];
		}
	}
	if(LOW[s]==DFN[s])
	{
		int cnt_node=0;
		int cnt_degree=0;
		do
		{
			j=st.top();
			st.pop();
			cnt_node++;
			cnt_degree+=indegree[k][j];
		}while(j!=s);
		if(cnt_node*2==cnt_degree)
			cnt_cir_node[k][cnt_cir[k]++]=cnt_node;
		else
			cnt_line_node[k][cnt_line[k]++]=cnt_node;
	}
}
void solve(int k)
{
	int i;
	cnt_line[k]=cnt_cir[k]=0;
	index_s=0;
	memset(LOW,-1,sizeof(LOW));
	memset(DFN,-1,sizeof(DFN));
	memset(instack,0,sizeof(instack));
	for(i=0;i<n[k];i++)	if(LOW[i]==-1)	Tarjan(k,i);
}
int main()
{
	int T,Case;
	int i;
	int ans;
	cin>>T;
	for(Case=1;Case<=T;Case++)
	{
		build_map(0);
		build_map(1);
		solve(0);
		solve(1);

		ans=0;
		if(cnt_line[0]!=cnt_line[1] || cnt_cir[0]!=cnt_cir[1])	ans=1;
		if(ans)	{printf("Case #%d: NO\n",Case);continue;}

		sort(cnt_line_node[0],cnt_line_node[0]+cnt_line[0]);
		sort(cnt_line_node[1],cnt_line_node[1]+cnt_line[1]);
		for(i=0;i<cnt_line[0];i++)	if(cnt_line_node[0][i]!=cnt_line_node[1][i])	{ans=1;break;}
		if(ans)	{printf("Case #%d: NO\n",Case);continue;}

		sort(cnt_cir_node[0],cnt_cir_node[0]+cnt_cir[0]);
		sort(cnt_cir_node[1],cnt_cir_node[1]+cnt_cir[1]);
		for(i=0;i<cnt_cir[0];i++)	if(cnt_cir_node[0][i]!=cnt_cir_node[1][i])	{ans=1;break;}
		if(ans)	printf("Case #%d: NO\n",Case);
		else	printf("Case #%d: YES\n",Case);
	}
	return 0;
}