//Let's join Kaede Takagaki Fan Club !! #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define int long long //#define L __int128 typedef long long ll; typedef pair P; typedef pair P1; typedef pair P2; #define pu push #define pb push_back #define eb emplace_back #define mp make_pair #define eps 1e-7 #define INF 1000000000 #define a first #define b second #define fi first #define sc second #define rng(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define rep(i,x) for(int i=0;i bool chmax(t&a,u b){if(a bool chmin(t&a,u b){if(b using vc=vector; template ostream& operator<<(ostream& os,const pair& p){ return os<<"{"< ostream& operator<<(ostream& os,const vc& v){ os<<"{"; for(auto e:v)os<> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } size_t operator()(pair x)const{ return operator()(uint64_t(x.first)<<32|x.second); } }; //unordered_set -> dtype, null_type //unordered_map -> dtype(key), dtype(value) using namespace __gnu_pbds; template using hash_table=gp_hash_table; template void g(T &a){ cin >> a; } template void o(const T &a,bool space=false){ cout << a << (space?' ':'\n'); } //ios::sync_with_stdio(false); const ll mod = 998244353; //const ll mod = 1000000007; mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count()); template void add(T&a,T b){ a+=b; if(a >= mod) a-=mod; } ll modpow(ll x,ll n){ ll res=1; while(n>0){ if(n&1) res=res*x%mod; x=x*x%mod; n>>=1; } return res; } #define _sz 1 ll F[_sz],R[_sz]; void make(){ F[0] = 1; for(int i=1;i<_sz;i++) F[i] = F[i-1]*i%mod; R[_sz-1] = modpow(F[_sz-1], mod-2); for(int i=_sz-2;i>=0;i--) R[i] = R[i+1] * (i+1) % mod; } ll C(int a,int b){ if(b < 0 || a < b) return 0; return F[a]*R[b]%mod*R[a-b]%mod; } int dp[105][105][105]; int n, m; vcsm[105], bg[105]; int cntsm[105], cntbg[105]; void dfssm(int v, int u){ cntsm[v] = 1; for(auto a:sm[v]) if(a != u){ dfssm(a, v); cntsm[v] += cntsm[a]; } } void dfsbg(int v, int u){ cntbg[v] = 1; for(auto a:bg[v]) if(a != u){ dfsbg(a, v); cntbg[v] += cntbg[a]; } } template< typename flow_t, typename cost_t > struct PrimalDual { const cost_t inf; struct edge{ int to; flow_t cap; cost_t cost; int rev; bool isrev; }; vc>g; vcpot, dist; vcprevv, preve; PrimalDual(int n): g(n), inf(numeric_limits::max()) {} void add_edge(int from, int to, flow_t cap, cost_t cost){ g[from].emplace_back((edge) {to, cap, cost, (int) g[to].size(), false}); g[to].emplace_back((edge) {from, 0, -cost, (int) g[from].size()-1, true}); } cost_t mcf(int s, int t, flow_t f){ int n = (int)g.size(); cost_t ret = 0; using pi = pair; priority_queue, greater>que; pot.assign(n, 0); preve.assign(n, -1); prevv.assign(n, -1); bool fs = true; while(f > 0){ dist.assign(n, inf); que.emplace(0, s); dist[s] = 0; while(!que.empty()){ pi p = que.top(); que.pop(); if(dist[p.sc] < p.fi) continue; rep(i, g[p.sc].size()){ edge &e = g[p.sc][i]; cost_t nc = dist[p.sc] + e.cost + pot[p.sc] - pot[e.to]; if(e.cap > 0 && dist[e.to] > nc){ dist[e.to] = nc; prevv[e.to] = p.sc, preve[e.to] = i; que.emplace(dist[e.to], e.to); } } } if(dist[t] == inf){ //can not send f units flow return -1; } rep(v, n) pot[v] += dist[v]; flow_t addflow = f; for(int v=t;v!=s;v=prevv[v]) chmin(addflow, g[prevv[v]][preve[v]].cap); f -= addflow; ret += addflow * pot[t]; for(int v=t;v!=s;v=prevv[v]){ edge &e = g[prevv[v]][preve[v]]; e.cap -= addflow; g[v][e.rev].cap += addflow; } } return ret; } void output(){ rep(i, g.size()){ for(auto &e:g[i]){ if(e.isrev) continue; auto &rev_e = g[e.to][e.rev]; cout << i << "->" << e.to << "(flow:" << rev_e.cap << "/" << rev_e.cap + e.cap << ")" << endl; } } } }; void solve(){ cin>>n; rep(i,n-1){ int a,b;cin>>a>>b; sm[a].pb(b); sm[b].pb(a); } cin>>m; rep(i,m-1){ int a,b;cin>>a>>b; bg[a].pb(b); bg[b].pb(a); } dfssm(1, -1); dfsbg(1, -1); vcsmv; repn(i, n) smv.pb(i); vc

bgv; repn(i, m) for(auto a:bg[i]) bgv.eb(i, a); sort(all(smv), [](int a, int b){ return cntsm[a] < cntsm[b]; }); sort(all(bgv), [](P a, P b){ int eva = (cntbg[a.a] > cntbg[a.b]?cntbg[a.b]:m-cntbg[a.a]); int evb = (cntbg[b.a] > cntbg[b.b]?cntbg[b.b]:m-cntbg[b.a]); return eva < evb; }); rep(i, 105) rep(j, 105) rep(k, 105) dp[i][j][k] = -INF; for(auto s:smv){ for(auto b:bgv){ int u = b.a, v = b.b; //calc dp[s][u][v] int eva = (cntbg[u] > cntbg[v]?cntbg[v]:m-cntbg[u]); for(auto ch:bg[v]){ //v, ch if(ch == u) continue; int evb = (cntbg[v] > cntbg[ch]?cntbg[ch]:m-cntbg[v]); if(eva < evb) continue; chmax(dp[s][u][v], dp[s][v][ch] + 1); } vcle, ri; for(auto ch:sm[s]) if(cntsm[ch] < cntsm[s]) le.pb(ch); for(auto ch:bg[v]) { if(ch == u) continue; int evb = (cntbg[v] > cntbg[ch]?cntbg[ch]:m-cntbg[v]); if(eva < evb) continue; ri.pb(ch); } if(le.size() > ri.size()) continue; PrimalDualpd(le.size()+ri.size()+5); int ss = le.size()+ri.size()+3; int t = ss+1; rep(i, le.size()){ rep(j, ri.size()){ if(dp[le[i]][v][ri[j]] < 0) continue; pd.add_edge(i, j+le.size(), 1, 1000 - dp[le[i]][v][ri[j]]); } } rep(i, le.size()) pd.add_edge(ss, i, 1, 0); rep(i, ri.size()) pd.add_edge(i+le.size(), t, 1, 0); auto ret = pd.mcf(ss, t, le.size()); if(ret < 0) continue; chmax(dp[s][u][v], (int)le.size() * 1000 - ret + (int)le.size()); } } int ans = -INF; repn(v, m){ int tmp = -INF; vcle, ri; for(auto ch:sm[1]) le.pb(ch); for(auto ch:bg[v]) ri.pb(ch); if(le.size() > ri.size()) continue; PrimalDualpd(le.size()+ri.size()+5); int s = le.size()+ri.size()+3; int t = s+1; rep(i, le.size()){ rep(j, ri.size()){ if(dp[le[i]][v][ri[j]] < 0) continue; pd.add_edge(i, j+le.size(), 1, 1000 - dp[le[i]][v][ri[j]]); } } rep(i, le.size()) pd.add_edge(s, i, 1, 0); rep(i, ri.size()) pd.add_edge(i+le.size(), t, 1, 0); auto ret = pd.mcf(s, t, le.size()); if(ret < 0) continue; tmp = (int)le.size() * 1000 - ret + (int)le.size(); chmax(ans, tmp); } if(ans < 0) ans = -1; o(ans); } signed main(){ cin.tie(0); ios::sync_with_stdio(0); cout<> t; while(t--) solve(); }