#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

std::ifstream in("lca.in");
std::ofstream out("lca.out");

#define SIZE 100001
#define LN_SIZE 21

struct Candidate {
    unsigned idx;
    unsigned depth;

    bool operator < (Candidate const& other) const {
        return this->depth < other.depth;
    }
};

unsigned ln[LN_SIZE];
Candidate dp[LN_SIZE][SIZE];

void init_rmq(Candidate const* vec, unsigned length) {
    ln[1] = 0;

    for(unsigned i = 2; i <= length; i += 1) {
        ln[i] = ln[i >> 1] + 1;
    }

    std::memcpy(dp[0], vec, length * sizeof(Candidate));

    for(unsigned pow = 1; pow < LN_SIZE && 1 << (pow - 1) < length; pow += 1) {
        unsigned start = 0;
        for(; start + (1 << (pow - 1)) < length; start += 1) {
            dp[pow][start] = std::min(
                dp[pow - 1][start + (1 << (pow - 1))],
                dp[pow - 1][start]
            );
        }
        for(; start + (1 << (pow - 1)) < length; start += 1) {
            dp[pow][start] = dp[pow - 1][start];
        }
    }
}

unsigned rmq(unsigned start, unsigned finish) {
    unsigned pow = ln[finish - start + 1];
    return std::min(
        dp[pow][start + (1 << (pow - 1))],
        dp[pow][start]
    ).idx;
}

using std::vector;

typedef vector<unsigned> node_t;
typedef vector<node_t> graph_t;

void init_candidates(graph_t& graph, unsigned root_idx, vector<Candidate>& candidates, unsigned depth = 0) {
    std::cout << depth << '\n';
    for(unsigned const& neighbour : graph[root_idx]) {
        candidates.push_back(
            Candidate {
                .idx = root_idx,
                .depth = depth
            }
        );
        init_candidates(graph, neighbour, candidates, depth + 1);
    }
    candidates.push_back(
        Candidate {
            .idx = root_idx,
            .depth = depth
        }
    );
}

// /// Returns the **index** of the lowest common ancestor.
// unsigned lca(graph_t& graph, unsigned root_idx, unsigned left, unsigned right) {
//     Candidate root = Candidate {
//         .idx = root_idx,
//         .depth = 0
//     };
//
//     vector<Candidate> candidates;
//     candidates.reserve((right - left + 1) << 2);
//
//     for()
// }

int main()
{
    unsigned N, M;
    in >> N >> M;

    vector<Candidate> candidates;
    graph_t graph;
    graph.resize(N);

    for(unsigned a, b, node = 1; node < N; node += 1) {
        in >> a >> b;
        graph[a - 1].push_back(b - 1);
    }

    init_candidates(graph, 1, candidates);
    init_rmq(&candidates[0], candidates.size());

    for(unsigned a, b, m = 0; m < M; m += 1) {
        in >> a >> b;
        out << (rmq(a - 1, b - 1) + 1) << '\n';
    }

    return 0;
}