AtCoder

分析

先考虑如果有一个点没有被操作过该怎么做。

我们把这个点作为根，在两棵树上分别 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;
}