#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <utility>
#include <stdlib.h>
#include <climits>
#include <dirent.h>
using namespace std;
#define max_n 100005
vector<int> first(max_n), euler_nodes, euler_levels;
vector<vector<int> > child(max_n), rmq;
int size, operations, a;
void make_euler(int node, int level) {
euler_nodes.push_back(node);
euler_levels.push_back(level);
first[node] = euler_nodes.size() - 1;
for (int i = 0; i < child[node].size(); i ++) {
make_euler(child[node][i], level + 1, first, euler_levels, euler_nodes, child);
euler_nodes.push_back(node);
euler_levels.push_back(level);
}
}
void constructTree (int start, int end, int poz, vector<int> &arbore) {
if (start == end) {
arbore[poz] = start;
return;
}
int doublePoz = poz << 1;
int mid = (start + end) >> 1;
constructTree(start, mid, doublePoz + 1, arbore, euler_levels);
constructTree(mid + 1, end, doublePoz + 2, arbore, euler_levels);
arbore[poz] = (euler_levels[arbore[doublePoz + 1]] <=
euler_levels[arbore[doublePoz + 2]] ? arbore[poz] = arbore[doublePoz + 1] :
arbore[poz] = arbore[doublePoz + 2]);
}
void findMax (int start, int end, int poz, int a, int b, vector<int> &arbore, int &sol, int &LCA_height) {
if (start >= a && b >= end) {
if (euler_levels[arbore[poz]] < LCA_height) {
sol = euler_nodes[arbore[poz]];
LCA_height = euler_levels[arbore[poz]];
}
return;
}
int mid = (start + end) >> 1;
int doublePoz = poz << 1;
if (a <= mid)
findMax(start, mid, doublePoz + 1, a, b, euler_nodes, euler_levels, arbore, sol, LCA_height);
if (b > mid)
findMax(mid + 1, end, doublePoz + 2, a, b, euler_nodes, euler_levels, arbore, sol, LCA_height);
}
int main() {
ifstream iFile("lca.in");
iFile >> size >> operations;
for (int i = 0; i < size - 1; i ++) {
iFile >> a;
child[a].push_back(i + 2);
}
make_euler(1, 0);
vector<int> arbore(euler_nodes.size() * 4);
constructTree(0, euler_nodes.size() - 1, 0, arbore);
ofstream oFile("lca.out");
for (int i = 0; i < operations; i ++) {
int u, v;
iFile >> u >> v;
int a = first[u], b = first[v];
if (a > b)
swap(a, b);
int LCA_height = INT_MAX, sol = INT_MAX;
findMax(0, euler_levels.size() - 1, 0, a, b, arbore, sol, LCA_height);
oFile << sol << endl;
}
return 0;
}