#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
const int SIZE = 1e5+10;

///ifstream cin("lca.in");
///ofstream cout("lca.out");

int n, m;
vector <int> v[SIZE];
vector <int> euler;
vector <int> rmq[20];
vector <int> p2;
int first[SIZE];
int depth[SIZE], cdepth;
int var, a, b;

void dfs(int nod = 1)
{
    ++cdepth;
    depth[nod] = cdepth;
    first[nod] = euler.size()+1;
    euler.push_back(nod);
    for(auto i : v[nod]) {
        dfs(i);
        euler.push_back(nod);
    }
    --cdepth;
}

void buildp2()
{
    p2.push_back(0);
    for(int i=1; i<euler.size()+20; i++) p2.push_back(p2[i/2]+1);
}

void buildRMQ()
{
    int lg = 1;
    while(1<<lg <= euler.size()) ++lg;
    lg--;
    for(auto i : euler) rmq[0].push_back(i);
    for(int i=1; i<=lg; i++) {
        for(int j=0; j+(1<<i)<euler.size(); j++)
            rmq[i].push_back((depth[rmq[i-1][j]]<depth[rmq[i-1][j+(1<<(i-1))]])? rmq[i-1][j] : rmq[i-1][j+(1<<(i-1))]);
    }
    for(int i=1; i<=lg; i++) {
        for(int j=0; j<rmq[i].size(); j++) cout<<rmq[i][j]<<' ';
        cout<<'\n';
    }
}

int query(int st, int dr)
{
    int lg = p2[dr-st+1]-1;
    if(depth[rmq[lg][st]]<depth[rmq[lg][dr+1-(1<<lg)]]) return rmq[lg][st];
    return rmq[lg][dr+1-(1<<lg)];
}

int qry(int a, int b)
{
    if(first[a]>first[b]) swap(a, b);
    return query(first[a], first[b]);
}

int main()
{
    cin>>n>>m;
    for(int i=2; i<=n; i++) {
        cin>>var;
        v[var].push_back(i);
    }
    dfs();
    buildRMQ();
    buildp2();
    for(int i=1; i<=n; i++) cout<<first[i]<<' ';
    cout<<'\n';
    for(int i=1; i<=m; i++)
        cin>>a>>b, cout<<qry(a, b)<<'\n';
    return 0;
}