#include #include #include #include #define overload4(_1, _2, _3, _4, name, ...) name #define rep1(i, n) for (ll i = 0; i < ll(n); ++i) #define rep2(i, s, n) for (ll i = ll(s); i < ll(n); ++i) #define rep3(i, s, n, d) for(ll i = ll(s); i < ll(n); i+=d) #define rep(...) overload4(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__) #define rrep1(i, n) for (ll i = ll(n)-1; i >= 0; i--) #define rrep2(i, n, t) for (ll i = ll(n)-1; i >= (ll)t; i--) #define rrep3(i, n, t, d) for (ll i = ll(n)-1; i >= (ll)t; i-=d) #define rrep(...) overload4(__VA_ARGS__,rrep3,rrep2,rrep1)(__VA_ARGS__) #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define SUM(a) accumulate(all(a),0LL) #define MIN(a) *min_element(all(a)) #define MAX(a) *max_element(all(a)) #define SORT(a) sort(all(a)); #define REV(a) reverse(all(a)); #define SZ(a) int(a.size()) #define popcount(x) __builtin_popcountll(x) #define pf push_front #define pb push_back #define ef emplace_front #define eb emplace_back #define ppf pop_front #define ppb pop_back #ifdef __LOCAL #define debug(...) { cout << #__VA_ARGS__; cout << ": "; print(__VA_ARGS__); cout << flush; } #else #define debug(...) void(0); #endif #define INT(...) int __VA_ARGS__;scan(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__) #define STR(...) string __VA_ARGS__;scan(__VA_ARGS__) #define CHR(...) char __VA_ARGS__;scan(__VA_ARGS__) #define DBL(...) double __VA_ARGS__;scan(__VA_ARGS__) #define LD(...) ld __VA_ARGS__;scan(__VA_ARGS__) using namespace std; using namespace __gnu_pbds; using ll = long long; using ld = long double; using P = pair; using LP = pair; using vi = vector; using vvi = vector; using vvvi = vector; using vl = vector; using vvl = vector; using vvvl = vector; using vd = vector; using vvd = vector; using vs = vector; using vc = vector; using vvc = vector; using vb = vector; using vvb = vector; using vp = vector

; using vvp = vector; using vlp = vector; using vvlp = vector; template using PQ = priority_queue, vector>, greater>>; template istream &operator>>(istream &is, pair &p) { return is >> p.first >> p.second; } template ostream &operator<<(ostream &os, const pair &p) { return os << '{' << p.first << ", " << p.second << '}'; } template istream &operator>>(istream &is, tuple &t) { return is >> get<0>(t) >> get<1>(t) >> get<2>(t); } template ostream &operator<<(ostream &os, const tuple &t) { return os << '{' << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << '}'; } template istream &operator>>(istream &is, vector &v) { for (T &t: v) { is >> t; } return is; } template ostream &operator<<(ostream &os, const vector &v) { os << '['; rep(i, v.size()) os << v[i] << (i == int(v.size() - 1) ? "" : ", "); return os << ']'; } template ostream &operator<<(ostream &os, const deque &v) { os << '['; rep(i, v.size()) os << v[i] << (i == int(v.size() - 1) ? "" : ", "); return os << ']'; } template ostream &operator<<(ostream &os, const set &st) { os << '{'; auto it = st.begin(); while (it != st.end()) { os << (it == st.begin() ? "" : ", ") << *it; it++; } return os << '}'; } template ostream &operator<<(ostream &os, const multiset &st) { os << '{'; auto it = st.begin(); while (it != st.end()) { os << (it == st.begin() ? "" : ", ") << *it; it++; } return os << '}'; } template ostream &operator<<(ostream &os, const map &mp) { os << '{'; auto it = mp.begin(); while (it != mp.end()) { os << (it == mp.begin() ? "" : ", ") << *it; it++; } return os << '}'; } template void vecout(const vector &v, char div = '\n') { rep(i, v.size()) cout << v[i] << (i == int(v.size() - 1) ? '\n' : div); } template bool constexpr chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template bool constexpr chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } void scan() {} template void scan(Head &head, Tail &... tail) { cin >> head; scan(tail...); } template void print(const T &t) { cout << t << '\n'; } template void print(const Head &head, const Tail &... tail) { cout << head << ' '; print(tail...); } template void fin(const T &... a) { print(a...); exit(0); } template vector &operator+=(vector &v, T x) { for (T &t: v) t += x; return v; } template vector &operator-=(vector &v, T x) { for (T &t: v) t -= x; return v; } template vector &operator*=(vector &v, T x) { for (T &t: v) t *= x; return v; } template vector &operator/=(vector &v, T x) { for (T &t: v) t /= x; return v; } struct Init_io { Init_io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout << boolalpha << fixed << setprecision(15); cerr << boolalpha << fixed << setprecision(15); } } init_io; const string yes[] = {"no", "yes"}; const string Yes[] = {"No", "Yes"}; const string YES[] = {"NO", "YES"}; const int inf = 1001001001; const ll linf = 1001001001001001001; void rearrange(const vi &) {} template void rearrange(const vi &ord, vector &head, Tail &...tail) { assert(ord.size() == head.size()); vector ori = head; rep(i, ord.size()) head[i] = ori[ord[i]]; rearrange(ord, tail...); } template void sort_by(vector &head, Tail &... tail) { vi ord(head.size()); iota(all(ord), 0); sort(all(ord), [&](int i, int j) { return head[i] < head[j]; }); rearrange(ord, head, tail...); } bool in_rect(int i, int j, int h, int w) { return 0 <= i and i < h and 0 <= j and j < w; } template vector cumsum(const vector &v, bool shift_one = true) { int n = v.size(); vector res; if (shift_one) { res.resize(n + 1); rep(i, n) res[i + 1] = res[i] + v[i]; } else { res.resize(n); if (n) { res[0] = v[0]; rep(i, 1, n) res[i] = res[i - 1] + v[i]; } } return res; } vvi graph(int n, int m, bool directed = false, int origin = 1) { vvi G(n); rep(_, m) { INT(u, v); u -= origin, v -= origin; G[u].pb(v); if (!directed) G[v].pb(u); } return G; } template vector>> weighted_graph(int n, int m, bool directed = false, int origin = 1) { vector>> G(n); rep(_, m) { int u, v; T w; scan(u, v, w); u -= origin, v -= origin; G[u].eb(v, w); if (!directed) G[v].eb(u, w); } return G; } class LCA { int n; vvi G; vi dep; vvi par; void dfs(int u, int p, int d) { par[0][u] = p; dep[u] = d; for (int v: G[u]) if (v != p) dfs(v, u, d + 1); } void init() { n = G.size(); dep.assign(n, -1); par.resize(30); rep(i, 30) par[i].resize(n); rep(i, n) if (dep[i] == -1) dfs(i, -1, 0); rep(k, 29) rep(i, n) { if (par[k][i] < 0) par[k + 1][i] = -1; else par[k + 1][i] = par[k][par[k][i]]; } } public: LCA(const vvi &G) : G(G) { init(); } int operator()(int u, int v) const { if (dep[u] > dep[v]) swap(u, v); rep(k, 30) if ((dep[v] - dep[u]) >> k & 1) v = par[k][v]; if (u == v) return u; rrep(k, 30) { if (par[k][u] != par[k][v]) { u = par[k][u]; v = par[k][v]; } } assert(par[0][u] == par[0][v]); return par[0][u]; } int la(int u, int d) const { rep(k, 30) if (d >> k & 1) u = par[k][u]; return u; } int dist(int u, int v) const { int w = this->operator()(u, v); return dep[u] + dep[v] - dep[w] * 2; } int depth(int u) const { return dep[u]; } // path from u to v (including u, v) vi path(int u, int v) const { int l = this->operator()(u, v); vi ul, vl; while (l != u) { ul.pb(u); u = par[0][u]; } while (l != v) { vl.pb(v); v = par[0][v]; } ul.pb(l); ul.insert(ul.end(), rall(vl)); return ul; } }; int main() { INT(n, q); vvi G = graph(n, n - 1); vi sub(n, 1); auto dfs = [&](auto &dfs, int u, int p) -> void { for (int v: G[u]) { if (v == p) continue; dfs(dfs, v, u); sub[u] += sub[v]; } }; dfs(dfs, 0, -1); LCA lca(G); while (q--) { INT(s, t); --s, --t; int l = lca(s, t); int d = lca.dist(s, t); if (d & 1) { print(0); continue; } if (lca.depth(s) < lca.depth(t)) swap(s, t); int ans = sub[lca.la(s, d / 2)]; if (lca.depth(s) == lca.depth(t)) { ans -= sub[lca.la(s, d / 2 - 1)]; ans -= sub[lca.la(t, d / 2 - 1)]; } else { ans -= sub[lca.la(s, d / 2 - 1)]; } print(ans); } }