#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=1005; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')t=-1;ch=getchar(); }while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m; struct node { int x,y; node(int _x,int _y){ x=_x,y=_y; } }; vector<node>g[maxn]; vector<int>v[maxn],P[maxn]; struct ds { struct SegTree { struct node { int lz,sm,len; node(){ lz=sm=0; } }d[maxn<<2]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) #define lz(p) d[p].lz #define sm(p) d[p].sm #define len(p) d[p].len void pu(int p){ sm(p)=sm(ls(p))+sm(rs(p)); }void cl(int p,int x){ lz(p)+=x,sm(p)+=x*len(p); }void pd(int p){ cl(ls(p),lz(p)),cl(rs(p),lz(p)),lz(p)=0; }void bd(int l,int r,int p){ len(p)=r-l+1;lz(p)=sm(p)=0; if(l==r)return; int mid=l+r>>1; bd(l,mid,ls(p)),bd(mid+1,r,rs(p)); }void upd(int l,int r,int s,int t,int p,int x){ if(l>r)return; if(l<=s&&t<=r){ cl(p,x);return; }pd(p);int mid=s+t>>1; if(l<=mid)upd(l,r,s,mid,ls(p),x);if(r>=mid+1)upd(l,r,mid+1,t,rs(p),x);pu(p); }int qry(int l,int r,int s,int t,int p){ if(l>r)return 0; if(l<=s&&t<=r)return sm(p); pd(p);int mid=s+t>>1,res=0; if(l<=mid)res+=qry(l,r,s,mid,ls(p));if(res)return res;if(r>=mid+1)res+=qry(l,r,mid+1,t,rs(p)); return res; } }T; int fa[maxn],dfn[maxn],siz[maxn],son[maxn],top[maxn],dep[maxn],ct; void dfs(int u){ siz[u]=1; for(int x:v[u])if(x!=fa[u])dep[x]=dep[u]+1,fa[x]=u,dfs(x),siz[u]+=siz[x]; for(int x:v[u])if(x!=fa[u]&&siz[x]>siz[son[u]])son[u]=x; } void dfs2(int u,int tp){ top[u]=tp,dfn[u]=++ct; if(!son[u])return;dfs2(son[u],tp); for(int x:v[u])if(x!=fa[u]&&x!=son[u])dfs2(x,x); } void init(){ dep[1]=1,dfs(1),dfs2(1,1),T.bd(1,n,1); } void upd(int x,int y,int w){ int tpx=top[x],tpy=top[y]; while(tpx!=tpy){ if(dep[tpx]>=dep[tpy])T.upd(dfn[tpx],dfn[x],1,n,1,w),x=fa[tpx]; else T.upd(dfn[tpy],dfn[y],1,n,1,w),y=fa[tpy]; tpx=top[x],tpy=top[y]; } if(dfn[x]>dfn[y])swap(x,y); T.upd(dfn[x]+1,dfn[y],1,n,1,w); } int qry(int x,int y){ int res=0; int tpx=top[x],tpy=top[y]; while(tpx!=tpy){ if(dep[tpx]>=dep[tpy])res+=T.qry(dfn[tpx],dfn[x],1,n,1),x=fa[tpx]; else res+=T.qry(dfn[tpy],dfn[y],1,n,1),y=fa[tpy]; if(res)return res; tpx=top[x],tpy=top[y]; } if(dfn[x]>dfn[y])swap(x,y); res+=T.qry(dfn[x]+1,dfn[y],1,n,1); return res; } int lca(int x,int y){ int tpx=top[x],tpy=top[y]; while(tpx!=tpy){ if(dep[tpx]>=dep[tpy])x=fa[tpx];else y=fa[tpy]; tpx=top[x],tpy=top[y]; } if(dep[x]>dep[y])swap(x,y); return x; } }T; bool mod(int x,int y){ if(T.qry(x,y))return 0; T.upd(x,y,1);return 1; } void slv(){ n=read();up(i,1,n-1){int x=read(),y=read();v[x].p_b(y),v[y].p_b(x);} T.init();m=read();while(m--){ int x=read(),y=read(); g[T.lca(x,y)].p_b(node(x,y)); } up(i,1,n)P[T.dep[i]].p_b(i); int res=0; while(clock()*1.0/CLOCKS_PER_SEC<0.5){ T.T.bd(1,n,1); int ret=0; down(i,n,1){ for(int x:P[i]){ int ct=50,mx=0; vector<node>qwq; while(ct--){ random_shuffle(g[x].begin(),g[x].end()); int cnt=0; vector<node>_; for(auto it:g[x])if(mod(it.x,it.y))_.p_b(it),cnt++; if(cnt>mx)qwq=_; mx=max(mx,cnt); for(auto it:_)T.upd(it.x,it.y,-1); } ret+=mx; for(auto it:qwq)mod(it.x,it.y); } }res=max(res,ret); } cout<<res<<'\n'; }int main(){ // freopen("celebration.in","r",stdin); // freopen("celebration.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }