#include using namespace std; using ll = long long; struct ReRooting{ using T = int; const T identity = 0; //mergeの演算に対する単位元 int n; vector> G; vector> dp; vector> dp2; vector ans; //vのi番目の辺の子からRを受け取ったときの処理 T receive(int v, int i, T &R){ return T(R); } //全体の累積lに子receiveの値をmerge //mergeの演算はモノイドでなくてはならない T merge(T l, T r){ return l + r; } //親に渡すときの処理 T givep(int v, T cum){ return cum + 1; } ReRooting() {} ReRooting(int N):n(N){ G.resize(N); dp.resize(N); dp2.resize(N); ans.resize(N,identity); } void add_edge(int a, int b) { G[a].emplace_back(b); G[b].emplace_back(a); } void read(){ int a, b; for(int i = 1; i < n; i++){ cin >> a >> b; a--, b--; G[a].emplace_back(b); G[b].emplace_back(a); } } void build() { for(int i = 0; i < n; i++){ sort(G[i].begin(), G[i].end()); } dfs(0); // 普通に木DP dfs2(0, identity); // 残りの部分木に対応するDPを計算 } T dfs(int v, int p = -1) { T res = identity; int deg = G[v].size(); dp[v] = vector(deg, identity); for (int i = 0; i < deg; i++) { int u = G[v][i]; if (u == p) continue; dp[v][i] = dfs(u, v); res = merge(res, receive(v, i, dp[v][i]) ); } return givep(v,res); } void dfs2(int v, const T& dp_p, int p = -1) { int deg = G[v].size(); for (int i = 0; i < deg; i++) { // 前のdfsで計算した有向辺に対応する部分木のDPを保存 if (G[v][i] == p){dp[v][i] = dp_p; break;} } vector dp_l(deg + 1, identity), dp_r(deg + 1, identity); // 累積merge for (int i = 0; i < deg; i++) { dp_l[i + 1] = merge(dp_l[i], receive(v, i, dp[v][i])); } dp2[v] = dp_l; for (int i = deg - 1; i >= 0; i--) { dp_r[i] = merge(dp_r[i + 1], receive(v, i, dp[v][i])); } ans[v] = dp_l[deg]; // 頂点 v の答え for (int i = 0; i < deg; i++) { // 一つ隣の頂点に対しても同様に計算 int u = G[v][i]; if (u == p) continue; dfs2(u, givep(v,merge(dp_l[i], dp_r[i + 1])),v); } } }; struct LCA_tree{ int _n,MAX_LOG_V,root; vector> g; vector> parent; vector depth; LCA_tree() : _n(0) {} LCA_tree(int n) : _n(n), g(n),depth(n) { MAX_LOG_V = 1; while(_n >> MAX_LOG_V) MAX_LOG_V++; parent.resize(MAX_LOG_V, vector(_n)); } void merge(int u, int v){ g[u].push_back(v); g[v].push_back(u); } void dfs(int v,int p,int d){ parent[0][v]=p; depth[v]=d; for(int i=0;idepth[v])swap(u,v); for(int i=0;i>i&1)v=parent[i][v]; } if(u==v)return u; for(int i=MAX_LOG_V-1;i>=0;i--){ if(parent[i][u]!=parent[i][v]){ u=parent[i][u]; v=parent[i][v]; } } return parent[0][u]; } //パスの辺数 int dist(int u,int v){ int lcav=lca(u,v); if(lcav==-1)return depth[u]+depth[v]; return depth[u]+depth[v]-2*depth[lcav]; } int la(int v, int k){ for(int j = MAX_LOG_V - 1; j >= 0; j--){ if(k >> j & 1){ v = parent[j][v]; } } return v; } array pos(int u, int v){ int lcav = lca(u, v); int dv = depth[u] + depth[v] - 2 * depth[lcav]; if(dv & 1) return array({-1, -1, -1}); dv /= 2; if(dv == depth[lcav] - depth[v]){ return array({lcav, la(v, dv - 1), la(u, dv - 1)}); } if(depth[lcav] - depth[v] < dv) swap(v, u); return array({lcav, la(v, dv - 1), la(u, dv + 1)}); } //頂点wが頂点u,vのパス上に存在するか int on_path(int u,int v,int w){ return (dist(u,w)+dist(v,w)==dist(u,v)); } }; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; vector> g(n); for(int i = 1; i < n; i++){ int u, v; cin >> u >> v; g[--u].emplace_back(--v); g[v].emplace_back(u); } LCA_tree G1(n); ReRooting G2(n); G1.g = g; G2.G = g; G1.init(0); G2.build(); auto f = [&](int v, int u){ int j = lower_bound(G2.G[v].begin(), G2.G[v].end(), u) - G2.G[v].begin(); return G2.dp[v][j]; }; while(q--){ int u, v; cin >> u >> v; u--, v--; auto b = G1.pos(u, v); if(b[0] == -1){ cout << 0 << '\n'; continue; } int ans = n; ans -= f(b[0], b[1]) + f(b[0], b[2]); cout << ans << '\n'; } }