#include <iostream>
#include <stdio.h>
#include <algorithm>

#define NMAX 100000
#define MMAX 2000000
#define LOGMAX 30
using namespace std;

int rmq [ LOGMAX ] [ NMAX + 1 ] ;
vector <int> g [ NMAX + 1 ] ;
int first [ NMAX + 1 ] ;
int depth [ NMAX + 1 ] ;
int deuler [ NMAX + 1 ] ;
vector <int> eu ;

void euler (int nod, int papa ) {
  if (nod != 1 )
    depth[nod] = depth[papa] + 1 ;
  eu.push_back(nod) ;
  for (auto y : g[nod] ) {
    if (y != papa ) {
      euler(y, nod) ;
      eu.push_back(nod) ;
    }
  }
}

void Rmq_init (int n) {
  int i, j ;
  for (i = 0 ; i < n ; i++ )
    rmq[0][i] = i ;
  for (j = 1 ; (1 << j) <= n ; j++ ) {
    for (i = 0 ; i + (1 << j) - 1 < n ; i++ )
      rmq[j][i] = rmq[j-1][i] ;
      if (deuler[rmq[j-1][i]] > deuler[rmq[j-1][i+(1<<(j-1))]] )
        rmq[j][i] = rmq[j-1][i+(1<<(j-1))] ;
  }
}

int log2 (int n ) {
  int p, exp ;
  exp = 0 ;
  p = 1 ;
  while ( p <= n ) {
    p = p * 2 ;
    exp++;
  }
  exp--;
  return exp ;
}

int Lca (int a, int b) {
  int k ;
  if (first[b] < first[a] )
    swap (b, a) ;
  k = log2 (first[b] - first[a] + 1 ) ;
  if (deuler[rmq[k][first[a]]] <= deuler[rmq[k][ first[b] - (1<<k)] ])
    return eu[rmq[k][first[a]]] ;
  else
    return eu[rmq[k][first[b] - (1<<k)]] ;
}

int main() {

  FILE *fin, *fout ;
  fin = fopen ("lca.in", "r" ) ;
  fout = fopen ("lca.out", "w" ) ;
  int n, i, tata, m, a, b, k ;
  fscanf (fin, "%d%d", &n, &m ) ;
  for (i = 2 ; i <= n ; i++ ) {
    fscanf (fin, "%d", &tata ) ;
    g[tata].push_back(i) ;
    g[i].push_back(tata) ;
  }
  euler(1, 0) ;
  for (i = 0 ; i < eu.size() ; i++ ) {
    if (first[eu[i]] == 0 )
      first[eu[i]] = i+1 ;
    fprintf (fout, "%d ", eu[i] ) ;
  }
  fprintf (fout, "\n" ) ;
  for (i = 0 ; i < eu.size() ; i++ ) {
    deuler[i] = depth[eu[i]] ;
    fprintf (fout, "%d ", depth[eu[i]] ) ;
  }
  fprintf (fout, "\n" ) ;
  Rmq_init(eu.size()) ;
  for (i = 0 ; i < m ; i++ ) {
    fscanf (fin, "%d%d", &a, &b ) ;
    fprintf (fout, "%d\n", Lca(a, b) ) ;
  }
  return 0;
}