#include #include using namespace std; int N; vectorG[1<<17]; vectore; int L[1<<17],R[1<<17]; int pr[17][1<<17],dep[1<<17]; void dfs(int u,int p,int d) { L[u]=e.size(); e.push_back(u); dep[u]=d; pr[0][u]=p; for(int v:G[u])if(v!=p)dfs(v,u,d+1); R[u]=e.size(); e.push_back(u); } int sum[2<<17]; main() { cin>>N; for(int i=1;i>u>>v; u--,v--; G[u].push_back(v); G[v].push_back(u); } dfs(0,-1,0); for(int k=1;k<17;k++)for(int i=0;i>Q; vectormi; for(;Q--;) { int a,b;cin>>a>>b; a--,b--; int lca; { int u=a,v=b; if(dep[u]>dep[v]) { int t=u;u=v;v=t; } for(int k=0;k<17;k++)if(dep[v]-dep[u]>>k&1)v=pr[k][v]; if(u==v)lca=u; else { for(int k=17;k--;)if(pr[k][u]!=pr[k][v]) { u=pr[k][u]; v=pr[k][v]; } lca=pr[0][u]; } } mi.push_back(lca); sum[L[lca]]+=2; sum[R[a]]--; sum[R[b]]--; } for(int i=0;i