This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/lca"
#include "../../code/graphs/LCABL.cc"
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int n, q;
cin >> n >> q;
vvi adj(n);
F0R(i, n - 1) {
int u;
cin >> u;
adj[i + 1].pb(u);
adj[u].pb(i + 1);
}
LCA lca(adj);
while(q--) {
int u, v;
cin >> u >> v;
cout << lca.query(u, v) << endl;
}
}
#line 1 "tests/yosupo/binary_lifting.lca.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/lca"
#line 1 "code/template.cc"
// this line is here for a reason
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define endl '\n'
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(x) (int)(x).size()
#define FOR(a, b, c) for (auto a = (b); (a) < (c); ++(a))
#define F0R(a, b) FOR (a, 0, (b))
template <typename T>
bool ckmin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <typename T>
bool ckmax(T& a, const T& b) { return a < b ? a = b, true : false; }
#ifndef DEBUG
#define DEBUG 0
#endif
#define dout if (DEBUG) cerr
#define dvar(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#line 2 "code/graphs/LCABL.cc"
struct LCA {
int n, logN, root;
vvi up;
vi h;
LCA(vvi& adj, int r = 0)
: n{SZ(adj)}, logN{31 - __builtin_clz(n)},
root{r}, up(n, vi(logN + 1, root)),
h(n, -1) {
build(adj);
}
void build(vvi& adj) {
queue<int> q;
q.push(root);
h[root] = 0;
while (SZ(q)) {
int v = q.front();
q.pop();
for (int u : adj[v])
if (h[u] == -1) {
h[u] = h[v] + 1;
q.push(u);
up[u][0] = v;
}
}
FOR (exp, 1, logN + 1)
F0R (v, n)
if (up[v][exp - 1] != -1)
up[v][exp] = up[up[v][exp - 1]][exp - 1];
}
int jumpUp(int v, int amt) {
for (int i = 0; v != -1 && (1 << i) <= amt; ++i)
if (amt & (1 << i))
v = up[v][i];
return v;
}
int query(int v, int u) {
v = jumpUp(v, max(0, h[v] - h[u]));
u = jumpUp(u, max(0, h[u] - h[v]));
if (u == v) return u;
for (int l = logN; ~l; --l) {
int jmpU = up[u][l], jmpV = up[v][l];
if (jmpU == -1 || jmpV == -1) continue;
if (jmpU != jmpV) {
u = jmpU;
v = jmpV;
}
}
return up[v][0];
}
};
#line 4 "tests/yosupo/binary_lifting.lca.test.cpp"
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int n, q;
cin >> n >> q;
vvi adj(n);
F0R(i, n - 1) {
int u;
cin >> u;
adj[i + 1].pb(u);
adj[u].pb(i + 1);
}
LCA lca(adj);
while(q--) {
int u, v;
cin >> u >> v;
cout << lca.query(u, v) << endl;
}
}