/*
Cel mai apropiat stramos comun
Varianta de 100p cu range minimum query
Se parcurge arborele de n noduri in adancime si se formeaza reprezentarea lui Euler. Pentru fiecare nod se retine si nivelul.
Cel mai apropiat stramos comun al nodurilor x si y va fi nodul situat pe cel mai mic nivel din reprezentarea Euler intre prima
aparitie a lui x in reprezentare si prima aparitie a lui y.

Vectorul euler va retine reprezentarea.
Vectorul nivel[i] va retine nivelul pe care se afla nodul scris la pozitia i in euler. Primul nivel este 0.
Matricea arb va retine pe fiecare linie i fiecare fiu al nodului i. E de preferat fata de matricea de adiacenta datorita
absentei zerourilor.
Vectorul prima[i] va retine indicele primei aparitii a nodului i in vectorul euler
Este necesar sa retinem intr-un vector si cea mai apropiata putere a lui 2 fata de o pozitie i din euler.
Vom folosi vectorul putere cu definitia putere[i]=j, unde 2^j<=i

Matricea a contine preprocesarea specifica algoritmului de rmq
a[i][j]=indexul nodului de nivel minim dintre pozitiile j si j+2^i-1 ale vectorului euler
Matricea se formeaza dupa formula

a[i][j] = j, daca i=0
        = minimul pe nivel al lui a[i-1][j]si a[i-1][j+2^i-1], in rest
Deoarece i va retine puteri ale lui 2,
el va merge de la 0 pana la ultima valoare in care 2^i<ultima pozitia din euler (o notam cu sf)
Din constructia matricei, deducem ca pe fiecare linie j va lua valori de la 1 pana la sf-2^i

Pentru gasirea celui mai mic stramos comun al nodurilor x si y se gaseste pozitia de nivel minim din secventa
prima[x]....prima[y]. Mai intai calculam diferenta dintre indecsii prima[x] si prima[y] si aflam cea mai apropiata
putere a lui 2 fata de aceasta diferenta cu ajutorul vectorului putere. Notam cu dif, diferenta si power puterea.
Pozitia cautata va fi minimul pe nivel al valorilor a[power][x] si a[power][dif-2^power].
Nodul de pe pozitia gasita va fi solutia.

dfs -ul are complexitatea O(n), formarea matricei a O(n*log n), formarea lui putere log 2*n iar fiecare interogare se face in O(1).
Complexitatea finala O(n*log n) + m, unde m este numarul de interogari

*/
#include <fstream>
#include <vector>
#define dim 100005

using namespace std;

int n,m,sf;//nr de noduri, nr de interogari si ultima pozitie din euler
//pentru inmultiri si impartiri cu 2 folosim operatori pe biti deoarece sunt mai rapizi
//reprezentarea lui Euler nu poate avea mai mult de 2*n elemente, la fel vectorii prima si putere
int euler[dim<<1],putere[dim<<1],prima[dim<<1];
//adancimea maxima a arborelui este n
int nivel[dim<<1];
//cea mai mare putere a lui 2 apropiata de 2*n este maxim 20, din acest motiv matricea a va avea maxim 20 linii si 2*n col
int a[20][dim<<2];
//matricea arbore poate avea maxim n linii, iar coloanele se vor construi la citire
vector<int>arb[dim];

ifstream fin("lca.in");
ofstream fout("lca.out");

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

void dfs(int nod, int niv)
{
    //introduc in euler nodul parcurs
    euler[++sf]=nod;
    //completez nivelul pentru indexul din euler
    nivel[sf]=niv;
    //retin indexul primei aparitii a lui nod in euler
    prima[nod]=sf;
    //parcurg toti fiii cu ajutorul unui iterator, ei se gasesc pe linia nod
    for(vector<int>::iterator it=arb[nod].begin();it!=arb[nod].end();it++)
    {
        dfs(*it,niv+1);
        //la revenirea spre parinte, il parcurg si marchez nivelul
        euler[++sf]=nod;
        nivel[sf]=niv;
    }

}

void rmq()
{
    int i,j;
    //formez vectorul putere, putere [1]=0
    for(i=2;i<=sf;i++)
        putere[i]=putere[i>>1]+1;
    //formez matricea a
    //completez linia 0
    for(i=1;i<=sf;i++)
        a[0][i]=i;
    //completez celelalte linii
    for(i=1;(1<<i)<sf;i++)
    {
        int k=(1<<i);
        for(j=1;j<=sf-k;j++)
        {
            int k1=(1<<(i-1));
            if(nivel[a[i-1][j]]<nivel[a[i-1][j+k1]])
                a[i][j]=a[i-1][j];
            else
                a[i][j]=a[i-1][j+k1];
        }

    }
}

int lca(int x, int y)
{
    int dif, power,k,aux,solutie;
    x=prima[x],y=prima[y];
    if(x>y)
    {
        aux=x;
        x=y;
        y=aux;
    }
    dif=y-x+1;
    power=putere[dif];
    k=(1<<power);
    if(nivel[a[power][x]]<nivel[a[power][x+dif-k]])
        solutie=a[power][x];
    else
        solutie=a[power][x+dif-k];
    return euler[solutie];
}

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