#include <bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back #define rep(i, l, r) for (int i = l; i <= r; ++i) #define per(i, r, l) for (int i = r; i >= l; --i) template <typename T> inline void chmin(T &x, const T &y) { if (x > y) x = y; } template <typename T> inline void chmax(T &x, const T &y) { if (x < y) x = y; } #define gc (c = getchar()) int read() { char c; while (gc < '-') ; if (c == '-') { int x = gc - '0'; while (gc >= '0') x = x * 10 + c - '0'; return -x; } int x = c - '0'; while (gc >= '0') x = x * 10 + c - '0'; return x; } const int N = 1e3 + 5, M = N * (N - 1) / 2, U = 1 << 10; int num[N], lk[N][11], u[N]; int dfn[N], sz[N], q[N], tot; int fa[N], deep[N], son[N], top[N]; int t[N]; struct edge { int x, y, bx, by, next; } l[M]; void dfs(int x, int fr, int dep) { fa[x] = fr; deep[x] = dep; sz[x] = 1; ++tot; q[tot] = x; dfn[x] = tot; int nnum = 0; rep(i, 0, num[x] - 1) { int y = lk[x][i]; if (y != fr) lk[x][nnum++] = y; } num[x] = nnum; u[x] = (1 << nnum) - 1; rep(i, 0, nnum - 1) { int y = lk[x][i]; dfs(y, x, dep + 1); sz[x] += sz[y]; if (sz[y] > sz[son[x]]) son[x] = y; } } void dfs2(int x, int ntop) { top[x] = ntop; rep(i, 0, num[x] - 1) { int y = lk[x][i]; dfs2(y, y == son[x] ? ntop : y); } } #define fx top[x] #define fy top[y] int qiu_lca(int x, int y) { while (fx != fy) { if (deep[fx] > deep[fy]) x = fa[fx]; else y = fa[fy]; } return deep[x] < deep[y] ? x : y; } int lo[U]; int id[N], dp[N][U], s[N]; int cnt[N]; int qcnt[11]; struct E { int s, u; }; E lkq[11][M]; bool cnt_xiao(int x, int y) { return cnt[x] < cnt[y]; } int b[N]; void Dp(int x) { rep(i, 0, num[x] - 1) Dp(lk[x][i]); rep(i, dfn[x] + 1, dfn[x] + sz[x] - 1) { int y = q[i]; if (fa[y] == x) s[y] += dp[y][u[y]]; else { int nb = fa[b[y]]; s[y] += dp[nb][u[nb] - (1 << id[b[y]])]; b[y] = nb; } } for (int i = t[x]; i; i = l[i].next) { ++cnt[l[i].bx]; ++cnt[l[i].by]; } sort(lk[x], lk[x] + num[x], cnt_xiao); rep(i, 0, num[x] - 1) id[lk[x][i]] = i; memset(qcnt, 0, sizeof(qcnt)); for (int i = t[x]; i; i = l[i].next) { int bx = l[i].bx = b[l[i].x], by = l[i].by = b[l[i].y]; int ns = s[l[i].x] + s[l[i].y]; if (!bx) swap(bx, by); if (!by) lkq[id[bx]][++qcnt[id[bx]]] = (E){ ns, 1 << id[bx] }; else { bx = id[bx]; by = id[by]; if (bx < by) swap(bx, by); ++qcnt[by]; lkq[by][qcnt[by]] = (E){ ns, (1 << bx) + (1 << by) }; } } rep(j, 1, u[x]) { int bx = lo[j & -j]; dp[x][j] = dp[x][j - (1 << bx)] + dp[lk[x][bx]][u[lk[x][bx]]]; rep(i, 1, qcnt[bx]) if ((j | lkq[bx][i].u) == j) chmax(dp[x][j], dp[x][j - lkq[bx][i].u] + lkq[bx][i].s + 1); } b[x] = x; } int main() { // freopen("celebration.in", "r", stdin); // freopen("celebration.out", "w", stdout); int n, m; cin >> n; rep(i, 1, n - 1) { int x, y; scanf("%d%d", &x, &y); lk[x][num[x]++] = y; lk[y][num[y]++] = x; } dfs(1, 0, 1); dfs2(1, 1); cin >> m; rep(i, 1, m) { int x, y; scanf("%d%d", &x, &y); int lca = qiu_lca(x, y); l[i].x = x; l[i].y = y; l[i].next = t[lca]; t[lca] = i; } for (int i = 1, j = 0; i < U; i <<= 1, ++j) lo[i] = j; Dp(1); cout << dp[1][u[1]]; }