#include <fstream>
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

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

int n,m,i,j,k,E[200001],N[100001],F[100001],P[200001],x,y,z;
vector <int> l[100001];
int D[20][100001];

void dfs(int nod,int niv){

    E[++k]=nod;
    N[k]=niv;
    F[nod]=k;

    for(int i=0;i<l[nod].size();i++){
            dfs(l[nod][i],niv+1);
            E[++k]=nod;
            N[k]=niv;
    }
}

int main(){
    fin>>n>>m;

    for(i=2;i<=n;i++){
        fin>>j;
        ///l[i].push_back(j);
        l[j].push_back(i);
    }

    dfs(1,1);

    for(i=1;i<=k;i++)
        cout<<E[i]<<" ";
    cout<<"\n";
    for(i=1;i<=k;i++)
        cout<<N[i]<<" ";
    //return 0;
    P[1]=0;
    for(i=2;i<=k;i++)
        P[i]=1+P[i/2];

    for(i=1;i<=k;i++)
        D[0][i]=i;

    for(i=1;i<=P[k];i++){
        for(j=1;j<=k;j++){
            D[i][j]=D[i-1][j];

            if( j+(1<<(i-1))<=k && N[ D[i][j] ]>N[ D[i-1][j+(1<<(i-1))]] )
                D[i][j]=D[i-1][j+(1<<(i-1))];
        }
    }

    for(;m;m--){
        fin>>x>>y;
        x=F[x];
        y=F[y];

        if(x>y)
            swap(x,y);

        z=P[y-x+1];

        //fout<<E[ min(N[ D[z][x] ], N[ D[z][y-(1<<z)+1] ]) ]<<"\n";
        if(N[ D[z][x] ] < N[ D[z][y-(1<<z)+1] ])
            fout<<E[D[z][x]]<<"\n";
        else
            fout<<E[D[z][y-(1<<z)+1]]<<"\n";
    }

    return 0;
}