/*#include <iostream>
#include <cmath>
#include <fstream>
using namespace std;
ifstream fin("rmq.in");
ofstream fout("rmq.out");

const int NMAX = 100000;
const int CMAX = log2(NMAX) + 1;
int RMQ[NMAX][CMAX];
int query(int x, int y) {
    x--;
    y--;
    int lung = y - x + 1;
    int logLung = int(log2(lung));
    return min(RMQ[x][logLung], RMQ[y - (1 << logLung) + 1][logLung]);

}
int main()
{
    int n, numQueries, x, y;
    fin >> n >> numQueries;
    for(int i = 0; i < n; i++)
        fin >> RMQ[i][0];
    for(int j = 1; j <= int(log2(n)); j++)
        for(int i = 0; i + (1 << j) <= n; i++)
            RMQ[i][j] = min(RMQ[i][j-1], RMQ[i+(1<<(j-1))][j-1]);
    for(int i = 0; i < numQueries; i++)
    {
        fin >> x >> y;
        fout << query(x,y) << "\n";
    }
    return 0;

}
*/
#include <iostream>
#include <cmath>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("lca.in");
const int NMAX = 100000;
const int CMAX = log2(NMAX) + 1;
int RMQ[NMAX][CMAX];
int euler[2*NMAX];
int nivele[2*NMAX];
int pozitii[NMAX];
vector<vector<int>> listaFii(NMAX + 1);
void computeRMQ(int n) {
    for(int i = 0; i < n; i++)
        RMQ[i][0] = i;
    for(int j = 1; j <= int(log2(n)); j++)
        for(int i = 0; i + (1 << j) <= n; i++)
            if(nivele[RMQ[i][j-1]] < nivele[RMQ[i+(1<<(j-1))][j-1]])
                RMQ[i][j] = RMQ[i][j-1];
            else RMQ[i][j] = RMQ[i+(1<<(j-1))][j-1];
            //RMQ[i][j] = min(RMQ[i][j-1], RMQ[i+(1<<(j-1))][j-1]);
}
int query(int x, int y) {
    //x--;
    x = pozitii[x];
    //y--;
    y = pozitii[y];
    if(x > y)
        swap(x,y);
    int lung = y - x + 1;
    int logLung = int(log2(lung));
    //return min(RMQ[x][logLung], RMQ[y - (1 << logLung) + 1][logLung]);
    if(nivele[RMQ[x][logLung]] < nivele[RMQ[y - (1 << logLung) + 1][logLung]])
        return euler[RMQ[x][logLung]];
    else return euler[RMQ[y - (1 << logLung) + 1][logLung]];
}
void computeListaFii(int n) {
    int tata;
    for(int i = 2; i < n + 1; i++)
    {
        fin >> tata;
        listaFii[tata].push_back(i);
    }
}
void parcurgereEuler(int currentNode, int nivel, int &k) {
    euler[k] = currentNode;
    pozitii[currentNode] = k;
    nivele[k++] = nivel;
    for(auto i: listaFii[currentNode]) {
        parcurgereEuler(i, nivel + 1, k);
        euler[k] = currentNode;
        nivele[k++] = nivel;
    }
}
int main()
{
    int n, numQueries, x, y;
    fin >> n >> numQueries;
    computeListaFii(n);
    int k = 0;
    parcurgereEuler(1, 0, k);
    for(int i = 0; i < k; i++)
        cout<<euler[i]<<" ";
    cout << "\n";
    computeRMQ(k);
    for(int i = 0; i < numQueries; i++)
    {
        fin >> x >> y;
        cout << query(x,y) << "\n";
    }
    return 0;

}