Shared code

/**
 *    author:  luminarae
 *    created: 23.01.2026 16:52:21
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

#define int int64_t
int LOG;

void dfs(int node, int par, vector<vector<int>> &graph, vector<vector<int>> &binl, vector<int> &depth) {
    for(auto child : graph[node]) {
        if(child == par) {
            continue;
        }
        depth[child] = depth[node] + 1;
        binl[child][0] = node;
        for(int i = 1; i < LOG; i++) {
            binl[child][i] = binl[binl[child][i - 1]][i - 1];
        }
        dfs(child, node, graph, binl, depth);
    }
}

int get_lca(int u, int v, vector<int> &depth, vector<vector<int>> &binl) {
    if(depth[u] < depth[v]) {
        swap(u, v);
    }
    int k = depth[u] - depth[v];
    for(int j = LOG - 1; j >= 0; j--) {
        if(k & (1LL << j)) {
            u = binl[u][j];
        }
    }
    if(u == v) {
        return u;
    }
    for(int j = LOG - 1; j >= 0; j--) {
        if(binl[u][j] != binl[v][j]) {
            u = binl[u][j];
            v = binl[v][j];
        }
    }
    return binl[u][0];
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    LOG = log2(n) + 1;
    vector<vector<int>> graph(n);
    vector<int> depth(n, 0);
    vector<vector<int>> binl(n, vector<int>(LOG));
    for(int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    dfs(0, -1, graph, binl, depth);
    while(q--) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        int x = get_lca(u, v, depth, binl);
        int dist = depth[u] + depth[v] - (2 * depth[x]);
        cout << dist << endl;
    }
    return 0;
}