#include <fstream>
#include <vector>
#include <iostream>
#define dim 100010
using namespace std;

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

int n,m,i,j,E[2*dim],N[2*dim],F[dim],k;
vector <int> l[dim];
int e,lung,rmq[20][2*dim],lg[2*dim];

void dfs(int nod, int niv){
    F[nod]=++k;
    N[k]=niv;
    E[k]=nod;

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

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

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

    for(i=1;i<=k;i++)
        cout<<E[i]<<" ";
    cout<<"\n";
    for(i=1;i<=k;i++)
        cout<<N[i]<<" ";
    cout<<"\n";

    for(i=2;i<=k;i++)
        lg[i]=lg[i/2]+1;

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

    for(e=1,lung=1; e<=lg[k]+1; e++,lung*=2){
        for(i=1;i<=k;i++){
            rmq[e][i]=rmq[e-1][i];

            if(i+lung<=k)
                if(N[rmq[e][i]]>N[rmq[e-1][i+lung]])
                    rmq[e][i]=rmq[e-1][i+lung];
        }
    }

    for(;m;m--){
        fin>>i>>j;

        i=F[i]; j=F[j];
        if(i>j)
            swap(i,j);

        lung=j-i+1;
        e=lg[lung];

        if(N[rmq[e][i]]<N[rmq[e][j-(1<<e)+1]])
            fout<<E[rmq[e][i]]<<"\n";
        else
            fout<<E[rmq[e][j-(1<<e)+1]]<<"\n";
    }

    return 0;
}