#include #define all(vec) vec.begin(),vec.end() #define mp make_pair using namespace std; using ll=long long; using P=pair; const ll INF=1LL<<30; const ll LINF=1LL<<62; const double eps=1e-9; const ll MOD=1000000007LL; templatevoid chmin(T &a,T b){a=min(a,b);}; templatevoid chmax(T &a,T b){a=max(a,b);}; templatevector make_v(size_t a){return vector(a);} templateauto make_v(size_t a,Ts... ts){return vector(ts...))>(a,make_v(ts...));} templatetypename enable_if::value==0>::type fill_v(T& t,const V& v){t=v;} templatetypename enable_if::value!=0>::type fill_v(T& t,const V& v){for(auto &e:t)fill_v(e,v);}; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; struct HLDecomposition{ int n,pos; vector> G; vector sum; vector nid,fst,hv,id,siz,dep,par; HLDecomposition(int n_):n(n_),pos(0),G(n),sum(n+10),nid(n,-1),fst(n,-1),hv(n,-1),id(n),siz(n,1),par(n,-1){} void add_edge(int u,int v){ G[u].push_back(v); G[v].push_back(u); } void build(int rt){ par[rt]=-1; dfs(rt); bfs(rt); } void dfs(int v){ int ma=0; for(auto u:G[v]){ if(u==par[v])continue; par[u]=v; dfs(u); siz[v]+=siz[u]; if(ma q; q.push(rt); while(!q.empty()){ int h=q.front();q.pop(); for(int i=h;i!=-1;i=hv[i]){ nid[i]=pos++; id[nid[i]]=i; fst[i]=h; for(auto j:G[i]){ if(j!=par[i]&&j!=hv[i]){ q.push(j); } } } } } void query(int u,int v){ while(1){ if(nid[u]>nid[v])swap(u,v); sum[max(nid[fst[v]],nid[u])]++; sum[nid[v]+1]--; if(fst[v]!=fst[u]){ v=par[fst[v]]; }else{ break; } } } ll ans(){ for(int i=1;i<=n;i++){ sum[i]+=sum[i-1]; } ll res=0; for(int i=0;i>n; HLDecomposition tree(n); for(int i=0;i>u>>v;--u;--v; tree.add_edge(u,v); } tree.build(0); int q;cin>>q; while(q--){ int u,v;cin>>u>>v;--u;--v; tree.query(u,v); } cout<