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

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

const int NMAX=100005;
const int LMAX=20;

int k,n,m;
int nivel[NMAX<<1],euler[NMAX<<1],prima_apar[NMAX];
vector<int> G[NMAX];

int rmq[NMAX<<1+1][LMAX];

void parcurgere(int nod, int nivel_curent){
    k++;
    euler[k]=nod;
    nivel[k]=nivel_curent;
    prima_apar[nod]=k;

    for(auto it: G[nod]){
        parcurgere(it,nivel_curent+1);
        k++;
        euler[k]=nod;
        nivel[k]=nivel_curent;
    }
}

void preProcesareRMQ(){
    for(int i=0; i<2*n; i++)
        rmq[i][0]=nivel[i];
    for(int j=1; (1<<j)<=2*n; j++){
        for(int i=0; i+(1<<j)-1<2*n; i++)
            rmq[i][j]=min(rmq[i][j-1],rmq[i+1<<(j-1)][j-1]);
    }
}

int query(int x, int y){
    int k=log2(y-x+1);
    return min(rmq[x][k],rmq[y-(1<<k)+1][k]);
}

int main()
{
    int x,y;
    fin>>n>>m;

    for(int i=2; i<=n; i++){
        fin>>x;
        G[x].push_back(i);
    }
    k=-1;
    parcurgere(1,0);
    for(int i=0; i<=k; i++)
        fout<<euler[i]<<" ";
    fout<<'\n';
    for(int i=0; i<=k; i++)
        fout<<nivel[i]<<" ";
    fout<<'\n';

    preProcesareRMQ();
    for(int i=0; i<m; i++){
        fin>>x>>y;
        int px=prima_apar[x];
        int py=prima_apar[y];
        if(px>py)
            swap(px,py);
        int level=query(px,py);
        bool gasit=false;
        for(int j=px; j<=py && !gasit; j++)
            if(nivel[j]==level)
                fout<<euler[j]<<'\n', gasit=true;
    }
    return 0;
}