#include <fstream>
#include <vector>
#define nmax 100000

using namespace std;

ifstream cin("lca.in");
ofstream cout("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()
{
    cin>>n>>m;
    for(int i=2; i<=n; i++)
    {
        int x;
        cin>>x;
        v[x].push_back(i);
    }
}

void dfs(int nod,int lvl) /// dfs euler
{
    E[++k]=nod;
    L[k]=lvl;
    First[nod]=k;
    if(v[nod].size()!=0)
    {
        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 p=1; (1<<p)<k; p++)
    {
        for(int j=1; j <= k-(1<<p); j++)
        {
            rmq[p][j]=rmq[p-1][j];
            int jnou=j+(1<<(p-1));
            if(L[rmq[p-1][j]]>L[rmq[p-1][jnou]])
            {
                rmq[p][j]=rmq[p-1][jnou];
            }
        }
    }
}

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;
        cin>>x>>y;
        cout<<lca(x,y)<<'\n';
    }
    return 0;
}