#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1009, M = 5e5 + 9; vector<int> G[N]; struct node { int u, v; } E[M]; int n, m, fa[N], siz[N], dep[N], son[N], top[N]; void dfs(int u) { dep[u] = dep[fa[u]] + 1, siz[u] = 1; for (int v : G[u]) { if (v == fa[u]) continue; fa[v] = u, dfs(v), siz[u] += siz[v]; if (siz[v] > siz[son[u]]) son[u] = v; } } void dfs(int u, int t) { top[u] = t; if (!son[u]) return; dfs(son[u], t); for (int v : G[u]) if (v != fa[u] && v != son[u]) dfs(v, v); } int LCA(int u, int v) { while (top[u] != top[v]) { if (dep[top[u]] < dep[top[v]]) swap(u, v); u = fa[top[u]]; } if (dep[u] > dep[v]) swap(u, v); return u; } vector<int> g[N], subT[N]; int dp[N][1029], full[N], bel[N], id[N], di[N], s[N], mx[N], Mx[N][N]; int ct[N], use[N][3], only[N], b[N]; void dfs2(int U, int cnt, int u, int c, int sta) { if (u >= cnt) { for (int i = 1; i <= c; i++) { if (ct[i] != 2) return; } int sum = 0; for (int i = 1; i <= c; i++) { sum += Mx[di[use[i][1]]][di[use[i][2]]]; } for (int i = 0; i < cnt; i++) { if (only[i]) sum += Mx[di[i]][0]; } dp[U][sta] = max(dp[U][sta], sum); return; } only[u] = 0; dfs2(U, cnt, u + 1, c, sta); use[c + 1][++ct[c + 1]] = u; dfs2(U, cnt, u + 1, c + 1, sta | (1 << u)); use[c + 1][ct[c + 1]--] = 0; for (int i = 1; i <= c; i++) { if (ct[i] > 1) continue; use[i][++ct[i]] = u; dfs2(U, cnt, u + 1, c, sta | (1 << u)); use[i][ct[i]--] = 0; } only[u] = 1; dfs2(U, cnt, u + 1, c, sta | (1 << u)); only[u] = 0; } void dfs1(int u) { int cnt = 0; for (int v : G[u]) { if (v == fa[u]) continue; dfs1(v), mx[v] = 0; } for (int v : G[u]) { if (v == fa[u]) continue; id[v] = cnt, di[cnt++] = v; for (int i : subT[v]) { subT[u].push_back(i), bel[i] = v; if (i == v) s[i] = dp[v][full[v]]; else s[i] += dp[v][full[v] ^ (1 << id[b[i]])], b[i] = fa[b[i]]; mx[v] = max(mx[v], s[i]); } } for (int i : g[u]) { int _u = E[i].u, _v = E[i].v; Mx[bel[_u]][bel[_v]] = max(Mx[bel[_u]][bel[_v]], s[_u] + s[_v] + 1); Mx[bel[_v]][bel[_u]] = max(Mx[bel[_v]][bel[_u]], s[_u] + s[_v] + 1); } dfs2(u, cnt, 0, 0, 0); full[u] = (1 << cnt) - 1, subT[u].push_back(u); for (int i = 0; i <= full[u]; i++) { for (int j = 0; j < cnt; j++) { if (!(i & (1 << j))) continue; int _i = i ^ (1 << j); dp[u][i] = max(dp[u][i], dp[u][_i]); } } b[u] = u; } int main() { scanf("%d", &n); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } dfs(1), dfs(1, 1); scanf("%d", &m); for (int i = 1; i <= m; i++) { scanf("%d%d", &E[i].u, &E[i].v); if (dep[E[i].u] < dep[E[i].v]) swap(E[i].u, E[i].v); g[LCA(E[i].u, E[i].v)].push_back(i); } dfs1(1); // for (int i = 1; i <= n; i++) cout << s[i] << ' '; // cout << endl; // for (int i = 0; i <= n; i++) { // for (int j = 0; j <= n; j++) { // cout << Mx[i][j] << ' '; // } // cout << endl; // } // cout << endl; // for (int i = 1; i <= n; i++) { // for (int j = 0; j <= full[i]; j++) { // cout << dp[i][j] << ' '; // } // cout << endl; // } printf("%d\n", dp[1][full[1]]); return 0; }