#include <bits/stdc++.h>

using namespace std;

ifstream fin("lca.in");
ofstream fout("lca.out");

const int NMAX = 1e5 + 7;
const int LMAX = 18;
vector<int> g[NMAX];

int root = 1;

vector<int> euler;
int inveuler[NMAX];
int depth[NMAX];

void liniarize(int node, int father, int cnt_depth) {
    depth[node] = cnt_depth; // Partea pentru Depth

    // Partea pentru liniarizare
    euler.push_back(node);
    for(auto son : g[node]) {
        if(son == father) continue;
        liniarize(son, node, cnt_depth + 1);
        euler.push_back(node);
    }
}

// pair<int, int> rmq[LMAX][(1 << LMAX)];
int rmq[LMAX][(1 << LMAX)];

// Comparator de la pair
/* bool operator <(pair<int, int> a, pair<int, int> b) {
    if(a.first == b.first)
        return a.second < b.second
    return a.first < b.first;
} */

void init_rmq() { // O(N * log(N))
    /// Ca sa nu avem probleme cu 0
    depth[0] = NMAX + 1;

    /// Copiem valorile in rmq
    for(int i = 0; i < euler.size(); i++) {
        rmq[0][i] = euler[i];
        inveuler[euler[i]] = i;
    }

    /// Precalculam RMQ
    for(int level = 1; level < LMAX; level++) {
        for(int i = 0; i + (1 << level) / 2 < euler.size(); i++) {
            int a = rmq[level - 1][i];
            int b = rmq[level - 1][i + (1 << level) / 2];
            if(depth[a] > depth[b]) rmq[level][i] = b;
            else rmq[level][i] = a;
        }
    }
}

int lg2(int length) {
    // __builtin_clz = count leading zero's
    return 31 - __builtin_clz(length);
}

int query_rmq(int a, int b) { // O(1) - complexitate constanta
    /// a si b sunt noduri

    int posa = inveuler[a];
    int posb = inveuler[b];

    if(posa > posb) swap(posa, posb);

    // Dam query pe [posa .. posb]

    int length = posb - posa + 1;

    int lg = lg2(length);

    // [posa .................................................. posb]
    // [posa ....... posa + (1 << lg)] = candidate a
    //              candidate b = [posb - (1 << lg) + 1 ....... posb]

    int cand_a = rmq[lg][posa];
    int cand_b = rmq[lg][posb - (1 << lg) + 1];

    if(depth[cand_a] > depth[cand_b]) return cand_b;
    else return cand_a;
}

int main() {
    assert((1 << LMAX) > 2 * NMAX);

    int n, m; fin >> n;
    int q; fin >> q;
    m = n - 1;
    for(int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    liniarize(root, -1, 1);
    init_rmq();

    for(int i = 0; i < q; i++)
    {
        int x, y; fin >> x >> y;
        fout << query_rmq(x, y) << endl;
    }
}