/*
Solutie 60pp
lowest common ancestor cu metoda smenului lui Batog
Vom imparti arborele in sqrt(h) intervale in functie de nivel. H va fi inaltimea arborelui sau pur si simplu o constanta.
Daca h=22, sqrt(20)=~4, prin urmare intervalele vor avea 4 inaltimi. De la 0 la 3, formam un interval, de la 4 la 7, altul,
de la 8 la 11, apoi 12 15, urmeaza 16, 19 si in final 20,21,22.
Pe langa tatal fiecarui nod, retinem si tatal intervalului din care face parte. Vectorul tataInt va fi folosit in acest scop,
iar vectorul tata va retine referintele ascendente.
Pentru a afla lca, urmarim sa aducem cele doua noduri in cadrul aceluiasi interval prin intermediul lui tataInt, iar apoi se
aplica metoda clasica
Complexitatea dfs este O(n), fiecare query se realizeaza in sqrt(n), deci complexitatea finala este O(m*sqrt(n))
Retinem graful in matricea fiilor numita arb
Memoria folosita este de ordinul O(n).
*/
#include<fstream>
#include<vector>

#define dim 100005

using namespace std;

//deoarece arborele poate avea maxim 100000 noduri, consideram h ca fiind o constanta
const int h=20;
int tata[dim],tataInt[dim],nivel[dim];
int n,m;
ifstream fin("lca.in");
ofstream fout("lca.out");

vector<int>arb[dim];

void citire()
{
    fin>>n>>m;
    int i,j;
    for(i=2;i<=n;i++)
    {
        fin>>j;
        tata[i]=j;
        arb[j].push_back(i);
    }
}

void dfs(int nod, int niv, int tataInterval)
{
    //tataInterval va fi tatal intervalului
    nivel[nod]=niv;
    tataInt[nod]=tataInterval;
    //daca nivelul se imparte exact la h, inseamna ca incepem un nou interval cu valoarea lui nod din acel moment ca tata
    if(niv%h==0)
        tataInterval=nod;
    for(vector<int>::iterator it=arb[nod].begin();it!=arb[nod].end();it++)
        dfs(*it,niv+1,tataInterval);
}

int lca(int x, int y)
{
    //mai intai urcam pe intervale pana cand x si y au acelasi tata de interval
    while(tataInt[x]!=tataInt[y])
        if(nivel[x]>nivel[y])
            x=tataInt[x];
        else
            y=tataInt[y];
    //in cadrul intervalului urcam pana cand gasim lca
    while(x!=y)
        if(nivel[x]>nivel[y])
            x=tata[x];
        else
            y=tata[y];
    return x;
}

int main()
{
    int x,y;
    citire();
    dfs(1,0,0);
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        fout<<lca(x,y)<<"\n";
    }
    return 0;
}