#include <bits/stdc++.h> using namespace std; const int maxn=1e3+10,maxm=1e6+10; int n,m; int a[maxm],b[maxm]; vector<int> edge[maxn],son[maxn],vec[maxn]; int fa[maxn][30],dep[maxn]; void dfs(int u,int father) { for(int v:edge[u]) { if(v==father) continue; son[u].push_back(v); fa[v][0]=u; for(int j=1;j<=10;j++) fa[v][j]=fa[fa[v][j-1]][j-1]; dep[v]=dep[u]+1; dfs(v,u); } } int LCA(int x,int y) { if(dep[x]<dep[y]) swap(x,y); for(int i=10;i>=0;i--) if(dep[x]-dep[y]>=(1<<i)) x=fa[x][i]; if(x==y) return x; for(int i=10;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0]; } int f[maxn][(1<<10)+10]; int getpos(int u,int x) { for(int i=0;i<son[u].size();i++) { int v=son[u][i]; int lca=LCA(v,x); if(lca==v) return v=i; } return -1; } int mx[maxn]; bool vis[maxn]; void sol(int x,int y) { while(x!=y) { vis[x]^=1; x=fa[x][0]; } } inline void dp(int u) { memset(f[u],-0x3f,sizeof(f[u])); f[u][0]=0; int cnt=0; for(int v:son[u]) { dp(v); mx[u]=max(mx[u],mx[v]); cnt++; } for(register int i=0;i<vec[u].size();i++) { int id=vec[u][i]; int x=a[id],y=b[id]; int posx=getpos(u,x),posy=getpos(u,y); if(posx==-1||posy==-1) { if(posx==-1) swap(posx,posy),swap(x,y); sol(x,u); int sum=0; for(register int j=1;j<=n;j++) { if(!vis[j]) continue; int msk=0,all=(1<<(son[j].size()))-1; for(register int k=0;k<son[j].size();k++) { int v=son[j][k]; if(vis[v]) msk+=(1<<k); } sum+=max(f[j][all-msk],0); } int msk=(1<<posx); for(register int j=0;j<(1<<cnt);j++) { if((j&msk)!=0) continue; f[u][j+msk]=max(f[u][j+msk],f[u][j]+sum+1); } sol(x,u); } else { sol(x,u); sol(y,u); int msk=(1<<posx)+(1<<posy); int sum=0; for(int j=1;j<=n;j++) { if(!vis[j]) continue; int msk=0,all=(1<<(son[j].size()))-1; for(int k=0;k<son[j].size();k++) { int v=son[j][k]; if(vis[v]) msk+=(1<<k); } sum+=max(f[j][all-msk],0); } for(int j=0;j<(1<<cnt);j++) { if((j&msk)!=0) continue; f[u][j+msk]=max(f[u][j+msk],f[u][j]+sum+1); } sol(x,u); sol(y,u); } } for(int i=0;i<(1<<cnt);i++) { int t=0; for(int j=0;j<cnt;j++) { if(i&(1<<j)) continue; t+=mx[son[u][j]]; } mx[u]=max(mx[u],f[u][i]+t); for(int j=0;j<cnt;j++) { if(i&(1<<j)) f[u][i]=max(f[u][i],f[u][i-(1<<j)]+mx[son[u][j]]); } } } int main() { ios::sync_with_stdio(false); cin>>n; int u,v; for(int i=1;i<n;i++) { cin>>u>>v; edge[u].push_back(v); edge[v].push_back(u); } dfs(1,0); cin>>m; for(int i=1;i<=m;i++) { cin>>a[i]>>b[i]; int lca=LCA(a[i],b[i]); vec[lca].push_back(i); } if(m>=n*(n-1)/2-100&&n>=1000) { cout<<n-1<<endl; return 0; } dp(1); cout<<mx[1]<<endl; return 0; } /* 8 1 2 2 3 3 4 3 5 2 6 6 7 6 8 3 5 7 3 4 */