Submission #3444542

---

Source Code Expand

//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
#define foreach(it,s) for(__typeof((s).begin()) it=(s).begin();it!=(s).end();it++)
#ifndef LOCAL
#define cerr if(0)cout
#endif
typedef long long ll;
const int mod=1e9+7;
//My i/o stream
struct fastio
{
	char s[100000];
	int it,len;
	fastio(){it=len=0;}
	inline char get()
	{
		if(it<len)return s[it++];it=0;
		len=fread(s,1,100000,stdin);
		if(len==0)return EOF;else return s[it++];
	}
	bool notend()
	{
		char c=get();
		while(c==' '||c=='\n')c=get();
		if(it>0)it--;
		return c!=EOF;
	}
}_buff;
#define geti(x) x=getnum()
#define getii(x,y) geti(x),geti(y)
#define getiii(x,y,z) getii(x,y),geti(z)
#define puti(x) putnum(x),putchar(' ')
#define putii(x,y) puti(x),puti(y)
#define putiii(x,y,z) putii(x,y),puti(z)
#define putsi(x) putnum(x),putchar('\n')
#define putsii(x,y) puti(x),putsi(y)
#define putsiii(x,y,z) putii(x,y),putsi(z)
inline ll getnum()
{
	ll r=0;bool ng=0;char c;c=_buff.get();
	while(c!='-'&&(c<'0'||c>'9'))c=_buff.get();
	if(c=='-')ng=1,c=_buff.get();
	while(c>='0'&&c<='9')r=r*10+c-'0',c=_buff.get();
	return ng?-r:r;
}
template<class T> inline void putnum(T x)
{
	if(x<0)putchar('-'),x=-x;
	register short a[20]={},sz=0;
	while(x)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1;i>=0;i--)putchar('0'+a[i]);
}
inline char getreal(){char c=_buff.get();while(c<=32)c=_buff.get();return c;}
ll qpow(ll x,ll k){return k==0?1:1ll*qpow(1ll*x*x%mod,k>>1)*(k&1?x:1)%mod;}
int Tn,n;
bool adj[55][55];
bool nadj[55][55];
bool vis[55],ty[55];
int fa[55];
void dfs(int x,bool flag)
{
	vis[x]=1;ty[x]=flag;
	for(int i=1;i<=n;i++)
	{
		if(adj[x][i]&&!vis[i])
		{
			fa[i]=x;
			dfs(i,flag&nadj[x][i]);
		}
	}
}
int mk[55],deg[55];
int q[233],qn;
void mark(int x,int c)
{
	mk[x]=c;
	for(int i=1;i<=n;i++)
	{
		if(nadj[x][i]&&mk[x]==2&&mk[i]==1)
		{
			q[qn++]=i;
			q[qn++]=x;
		}
		if(nadj[x][i]&&mk[x]==1&&mk[i]==2)
		{
			q[qn++]=x;
			q[qn++]=i;
		}
	}
}
int solve(int S)
{
	memset(vis,0,sizeof(vis));
	fa[S]=0;
	dfs(S,1);
	for(int i=1;i<=n;i++)if(!vis[i])return n+1;
	qn=0;
	memset(mk,0,sizeof(mk));
	memset(deg,0,sizeof(deg));
	for(int i=1;i<=n;i++)deg[fa[i]]++;
	for(int i=1;i<=n;i++)
	{
		if(ty[i])mark(i,2);
		else if(deg[i]==0)mark(i,1);
	}
	int cnt=0;
	for(int i=0;i<qn;i+=2)
	{
		int x=q[i],y=q[i+1];
		if(mk[x]==1)
		{
			cnt++;
			mark(x,2);
			deg[fa[x]]--;
			if(deg[fa[x]]==0&&mk[fa[x]]==0)mark(fa[x],1);
		}
	}
	for(int i=1;i<=n;i++)if(mk[i]!=2)return n+1;
	return cnt;
}
void solve()
{
	memset(adj,0,sizeof(adj));
	memset(nadj,0,sizeof(nadj));
	geti(n);
	for(int i=1;i<n;i++)
	{
		int x,y;
		getii(x,y);
		adj[x][y]=adj[y][x]=1;
	}
	bool same=1;
	for(int i=1;i<n;i++)
	{
		int x,y;
		getii(x,y);
		same&=adj[x][y];
		nadj[x][y]=nadj[y][x]=1;
	}
	if(same)
	{
		puts("0");
		return;
	}
	int ans=n+1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(!adj[i][j])continue;
			for(int k=1;k<=n;k++)
			{
				if(adj[i][k])continue;
				adj[i][j]=0;
				adj[i][k]=1;
				ans=min(ans,solve(i)+1);
				adj[i][j]=1;
				adj[i][k]=0;
			}
		}
	}
	if(ans>n)puts("-1");
	else cout<<ans<<endl;
}
int main()
{
	geti(Tn);
	while(Tn--)
	{
		solve();
	}
	return 0;
}

Submission Info

Judge Result