#include <iostream>
#include <fstream>
#include <vector>
#define Nmax 100000

using namespace std;

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

vector<int> v[Nmax+5];
int lg[2*Nmax +5],rmq[20][Nmax*4 + 5],E[Nmax*2 + 5],First[Nmax + 5],L[Nmax * 2 + 5];
int n,m,k;
void read()
{
    fin>>n>>m;
    for(int i=2;i<=n;i++)
    {
        int x;
        fin>>x;
        v[x].push_back(i);
    }
}

void dfs(int nod,int lvl)
{
    E[++k]=nod;
    L[k]=lvl;
    First[nod]=k;
    for(auto i : v[nod])
    {
        dfs(i,lvl+1);
        E[++k]=nod;
        L[k]=lvl;
    }
}

void Rmq()
{
    for(int i=2;i<=k;i++)
        lg[i]=lg[i/2]+1;
    for(int i=1;i<=k;i++)
        rmq[0][i]=i;
    for(int i=1;(1<<i)<k;i++)
    {
        for(int j=1; j <= k - (1 << i);j++)
        {
            rmq[i][j]=rmq[i-1][j];
            if(L[rmq[i-1][j]]>L[rmq[i-1][j+(1<<(i-1))]])
                rmq[i][j]=rmq[i-1][j+(1<<(i-1))];
        }
    }
}

int lca(int x , int y)
{
	int diff, l, sol, sh;
	int a = First[x], b = First[y];
	if(a > b) swap(a, b);
	diff = b - a + 1;
	l = lg[diff];
	sol = rmq[l][a];
	sh = diff - (1 << l);
	if(L[sol] > L[rmq[l][a + sh]])
		sol = rmq[l][a + sh];
	return E[sol];
}
int main()
{
    read();
    dfs(1,0);
    Rmq();
    for(int i=1;i<=k;i++)
        cout<<E[i]<<" ";
    cout<<'\n';
    cout<<k<<" "<<lg[k]<<'\n';
    for(int i=0;i<=lg[k];i++)
    {
        for(int j=1;j<=k;j++)
            cout<<L[rmq[i][j]]<<" ";
        cout<<'\n';
    }
    for(int i=1;i<=m;i++)
    {
        int x , y;
        fin>>x>>y;
        fout<<lca(x,y)<<'\n';
    }
    return 0;
}