分析
先考虑如果有一个点没有被操作过该怎么做。
我们把这个点作为根,在两棵树上分别 DFS 一遍,那么如果有解的话答案一定是在两棵树上父节点不同的点数。
现在的问题在于如何判无解。首先如果 A 中一个点不要被操作但它的父节点要被操作,那么一定是无解的。否则,考虑到 A 中一个点的父节点要在它之后被操作,B 中一个点的父节点要在它之前被操作,这样子就有若干个偏序关系,我们只需要拓扑排序判断是否有环即可。
然而有可能每个点都被操作过,于是我们先枚举一下第一次操作,这样子被操作的点在之后一定不会被操作,就可以用上面的做法了。
代码
// ====================================
// author: M_sea
// website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;
int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=50+10;
const int inf=0x3f3f3f3f;
int n;
struct V {
vector<int> E[N];
int deg[N];
void addEdge(int u,int v) {
E[u].emplace_back(v),++deg[v];
}
void init() {
for (int i=1;i<=n;++i) E[i].clear(),deg[i]=0;
}
int fa[N];
void dfs(int u,int f) {
fa[u]=f;
for (int v:E[u]) if (v!=f) dfs(v,u);
}
} A,B,G;
int check(int u) { return A.fa[u]==B.fa[u]; }
int calc() {
int res=0;
for (int i=1;i<=n;++i) if (!check(i)) ++res;
G.init();
for (int i=1;i<=n;++i) {
if (check(i)) {
if (!check(A.fa[i])) return inf;
else continue;
}
if (!check(A.fa[i])) G.addEdge(i,A.fa[i]);
if (!check(B.fa[i])) G.addEdge(B.fa[i],i);
}
queue<int> Q; int cnt=0;
for (int i=1;i<=n;++i) if (!G.deg[i]) Q.push(i);
while (!Q.empty()) {
int u=Q.front(); Q.pop(); ++cnt;
for (int v:G.E[u])
if (!--G.deg[v]) Q.push(v);
}
return cnt==n?res:inf;
}
int main() {
int T=read();
while (T--) {
n=read(); A.init(),B.init();
for (int i=1;i<n;++i) {
int u=read(),v=read();
A.addEdge(u,v),A.addEdge(v,u);
}
for (int i=1;i<n;++i) {
int u=read(),v=read();
B.addEdge(u,v),B.addEdge(v,u);
}
int ans=inf;
for (int i=1;i<=n;++i) {
A.dfs(i,0),B.dfs(i,0),ans=min(ans,calc());
if (A.deg[i]!=1) continue;
for (int j=1;j<=n;++j) {
if (i==j) continue;
A.dfs(j,i),A.fa[i]=0,ans=min(ans,calc()+1);
}
}
if (ans==inf) puts("-1");
else printf("%d\n",ans);
}
return 0;
}