LCA

#include <bits/stdc++.h>
#define TASK "LCA"
using namespace std;
const int N = 5e5;
int n, q, par[N+1], P[21][N+1], LG[N+1], depth[N+1];
vector<int> Adj[N+1];
void DFS(int u, int p)
{
    for (int v : Adj[u])
    {
        if (v == p)
        {
            continue;
        }
        P[0][v] = u;
        for (int k = 1; k <= LG[n]; ++ k)
        {
            P[k][v] = P[k-1][P[k-1][v]];
        }
        depth[v] = depth[u] + 1;
        DFS(v, u);
    }
}
void read()
{
   cin >> n >> q;
   LG[1] = 0;
   for (int i = 2; i <= N; ++ i)
   {
       LG[i] = LG[i/2] + 1;
   }
   for (int i = 1; i < n; ++ i)
   {
       cin >> par[i];
       Adj[par[i]].push_back(i);
   }
   DFS(0,0);
}
int LCA(int u, int v)
{
   if (depth[u] < depth[v])
   {
       swap(u, v);
   }
   int k = depth[u] - depth[v];
   for (int i = 0; i <= LG[n]; ++ i)
   {
       if (k & (1 << i))
       {
           u = P[i][u];
       }
   }
   if (u == v)
   {
       return u;
   }
   for (int i = LG[n]; i >= 0; -- i)
   {
       if (P[i][u] != P[i][v])
       {
           u = P[i][u];
           v = P[i][v];
       }
   }
   return P[0][u];
}
void solve()
{
   while(q--)
   {
       int u, v;
       cin >> u >> v;
       cout << LCA(u, v) << '\n';
   }
}

int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   //freopen(TASK".INP", "r", stdin);
   //freopen(TASK".OUT", "w", stdout);
   read();
   solve();
}