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

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

int Euler[200005],Level[200005],First[100002],Log[200005],RMQ[200005][19],n,m,k;
vector<int> G[100002];

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

void parcurgere(int nod,int level)
{
    Euler[++k]=nod;
    Level[k]=level;
    First[nod]=k;
    for(int i=0;i<G[nod].size();++i)
    {
        parcurgere(G[nod][i],level+1);
        Euler[++k]=nod;
        Level[k]=level;
    }
}
void rmq()
{
    RMQ[1][0]=1;
    for(int i=2; i<=k; ++i)
    {
        Log[i]=Log[i/2]+1;
        RMQ[i][0]=i;
    }

   for(int j=1;(1<<j)<k;++j)
        for(int i=1;i+(1<<j)<=k;++i)
        {
            int s=1<<(j-1);
            RMQ[i][j]=RMQ[i][j-1];
            if(Level[RMQ[i+s][j-1]]<Level[RMQ[i][j]])
                RMQ[i][j]=RMQ[i+s][j-1];
        }
}

int lca(int x,int y)
{
    int a=First[x],b=First[y];
    if(a>b)
        swap(a,b);
    int lg=Log[b-a+1];
    int sol=RMQ[a][lg];
    if(Level[sol]>Level[RMQ[b+1-(1<<lg)][lg]])
        sol=RMQ[b+1-(1<<lg)][lg];
    return Euler[sol];
}
int main()
{
    citire();
    parcurgere(1,0);
    rmq();
    for(int i=1;i<=2*n;++i)
        cout<<Euler[i]<<" ";
    cout<<"\n";
    for(int i=1;i<=2*n;++i)
        cout<<First[i]<<" ";

    int x,y;
    while(m--)
    {
        fin>>x>>y;
        fout<<lca(x,y)<<"\n";
    }
    return 0;
}