#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
const int NMAX = 1005;
const int POWMAX = 32;
int min(int a, int b) {
if (a < b) {
return a;
} else {
return b;
}
}
void make_query_scheme(int* numbers, int n, int** scheme) {
for (int i = 1; i <= n; ++i) {
scheme[0][i] = i;
}
for (int i = 1; (1 << i) <= n; ++i) {
for (int j = 1; j <= n - (1 << i) + 1; ++j) {
int l = 1 << (i - 1);
if (numbers[scheme[i - 1][j]] < numbers[scheme[i - 1][j + l]]) {
scheme[i][j] = scheme[i - 1][j];
} else if (numbers[scheme[i - 1][j]] > numbers[scheme[i - 1][j + l]]) {
scheme[i][j] = scheme[i - 1][j + l];
} else {
scheme[i][j] = min(scheme[i - 1][j], scheme[i - 1][j + l]);
}
}
}
}
void make_logmap(int* logmap, int n) {
logmap[1] = 0;
for (int i = 2; i <= n; ++i) {
logmap[i] = logmap[i / 2] + 1;
}
}
void dfs(int** tree, int* euler_tour, int* depths, int* first, int x, int depth) {
euler_tour[++euler_tour[0]] = x;
depths[++depths[0]] = depth;
first[x] = depths[0];
for (int i = 1; i <= tree[x][0]; ++i) {
dfs(tree, euler_tour, depths, first, tree[x][i], depth + 1);
if (i < tree[x][0]) {
euler_tour[++euler_tour[0]] = x;
depths[++depths[0]] = depth;
}
}
euler_tour[++euler_tour[0]] = x;
depths[++depths[0]] = depth;
}
void make_euler_tour(int** tree, int n, int* euler_tour, int* depths, int* first) {
euler_tour[0] = 0;
dfs(tree, euler_tour, depths, first, 1, 0);
}
int main() {
FILE* input_file = fopen("lca.in", "r");
FILE* output_file = fopen("lca.out", "w");
int n = 0, m = 0;
assert(fscanf(input_file, "%d", &n) == 1);
assert(fscanf(input_file, "%d", &m) == 1);
int* parents = (int*)malloc((n + 10) * sizeof(int));
int* children_count = (int*)malloc((n + 10) * sizeof(int));
// initialize children count 0
for (int i = 0; i <= n; ++i) {
children_count[i] = 0;
}
// read parent array and count children
for (int i = 2; i <= n; ++i) {
assert(fscanf(input_file, "%d", &parents[i]));
children_count[parents[i]] += 1;
}
// initialize tree
int** tree = (int**)malloc((n + 10) * sizeof(int*));
for (int i = 1; i <= n; ++i) {
tree[i] = (int*)malloc((children_count[i] + 10) * sizeof(int));
tree[i][0] = 0;
}
// fill tree
for (int i = 2; i <= n; ++i) {
int parent = parents[i];
tree[parent][++tree[parent][0]] = i;
}
// get euler tour and depths
int* euler_tour = (int*)malloc((3 * n + 10) * sizeof(int));
euler_tour[0] = 0;
int* depths = (int*)malloc((3 * n + 10) * sizeof(int));
depths[0] = 0;
int* first = (int*)malloc((n + 10) * sizeof(int));
make_euler_tour(tree, n, euler_tour, depths, first);
int** scheme = (int**)malloc(POWMAX * sizeof(int*));
for (int i = 0; i < POWMAX; ++i) {
scheme[i] = (int*)malloc((n + 10) * sizeof(int));
}
int* numbers = depths;
make_query_scheme(numbers, numbers[0], scheme);
int* logmap = (int*)malloc((depths[0] + 10) * sizeof(int));
make_logmap(logmap, depths[0]);
for (int i = 0; i < m; ++i) {
int x = 0, y = 0;
assert(fscanf(input_file, "%d", &x) == 1);
assert(fscanf(input_file, "%d", &y) == 1);
x = first[x]; y = first[y];
if (x > y) {
int temp = y;
y = x;
x = temp;
}
int diff = y - x + 1;
int l = logmap[diff];
int sh = diff - (1 << l);
int i1 = scheme[l][x];
int i2 = scheme[l][x + sh];
if (numbers[i1] < numbers[i2]) {
fprintf(output_file, "%d\n", euler_tour[i1]);
} else if (numbers[i1] > numbers[i2]) {
fprintf(output_file, "%d\n", euler_tour[i2]);
} else {
fprintf(output_file, "%d\n", euler_tour[min(i1, i2)]);
}
}
fclose(input_file);
fclose(output_file);
return 0;
}