1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
| #include<bits/stdc++.h>
#define rint register int
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<48||ch>57){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>=48&&ch<=57){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
vector<int>e[100],g[100];
int fa[100],ndeg[100],deg[100],vis[100],mp[100][100];
inline void dfs(int u,int f)
{
if(fa[u]=f,vis[f]&&mp[u][f])
{
vis[u]=1;
}
for(int v:g[u])
if(v^f) dfs(v,u);
}
inline void work()
{
int n=read();
int ans=n+1;
memset(mp,0,sizeof (mp));
for(rint i=1;i<=n;i++)
{
e[i].clear();
g[i].clear();
}
for(rint i=1;i<n;i++)
{
int u,v;
u=read();
v=read();
mp[u][v]=mp[v][u]=1;
e[u].push_back(v);
e[v].push_back(u);
}
for(rint i=1;i<n;i++)
{
int u,v;
u=read();
v=read();
g[u].push_back(v);
g[v].push_back(u);
}
for(rint i=1;i<=n;i++)
ndeg[i]=e[i].size();
for(rint i=1;i<=n;i++)
{
int cost=0,u;
memset(vis,0,4*n+4),vis[i]=1,dfs(i,0),memcpy(deg+1,ndeg+1,4*n);
while(14514)
{
for(u=1;u<=n;u++)
if(!vis[u]&°[u]==1&&vis[fa[u]]) break;
if(u>n) break;
else
{
vis[u]=1;
cost+=1;
}
for(int v:e[u]) --deg[v];
}
for(u=1;u<=n;u++) if(!vis[u]) break;
if(u>n) ans=min(ans,cost);
if(e[i].size()>1||u>n||ans<=n) continue;
memset(vis,0,4*n+4);
vis[0]=1;
memcpy(deg+1,ndeg+1,4*n);
while(14514)
{
for(u=1;u<=n;++u) if(!vis[u]&°[u]<=1&&vis[fa[u]]) break;
if(u>n) break; else vis[u]=1;
for(int v:e[u]) --deg[v];
}
for(u=1;u<=n;++u) if(!vis[u]) break;
if(u>n) ans=n;
}
if(ans>n) cout<<-1<<endl;
else cout<<ans<<endl;
}
int main(){
for(int T=read();T;T--)
work();
puts("");
return 0;
}
|
