#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int L = 18;
int n, q, ptr;
int lvl[N], par[N][L], eulerIndex[N], rmin[N][L], rmax[N][L], intervalLCA[N][L];
vector<int> g[N];
void dfs(int x, int p) {
  lvl[x] = lvl[p] + 1;
  eulerIndex[x] = ptr++;
  for (int ch : g[x]) {
    if (ch == p) continue;
    dfs(ch, x);
  }
}
int lca(int a, int b) {
  if (lvl[a] < lvl[b]) swap(a, b);
  if (lvl[a] > lvl[b]) {
    int d = lvl[a] - lvl[b];
    for (int j = 0; j < L; j++) {
      if (d & (1 << j)) a = par[a][j];
    }
  }
  if (a == b) return a;
  for (int j = L - 1; j >= 0; j--) {
    if (par[a][j] != par[b][j]) {
      a = par[a][j];
      b = par[b][j];
    }
  }
  return par[a][0];
}
void buildSparseTables() {
  for (int i = 1; i <= n; i++) {
    rmin[i][0] = rmax[i][0] = intervalLCA[i][0] = i;
  }
  for (int j = 1; (1 << j) <= n; j++) {
    for (int i = 1; i + (1 << j) - 1 <= n; i++) {
      int &r = rmin[i][j];
      int u = rmin[i][j - 1];
      int v = rmin[i + (1 << (j - 1))][j - 1];
      if (eulerIndex[u] < eulerIndex[v])
        r = u;
      else
        r = v;
    }
  }
  for (int j = 1; (1 << j) <= n; j++) {
    for (int i = 1; i + (1 << j) - 1 <= n; i++) {
      int &r = rmax[i][j];
      int u = rmax[i][j - 1];
      int v = rmax[i + (1 << (j - 1))][j - 1];
      if (eulerIndex[u] > eulerIndex[v])
        r = u;
      else
        r = v;
    }
  }
  for (int j = 1; (1 << j) <= n; j++) {
    for (int i = 1; i + (1 << j) - 1 <= n; i++) {
      intervalLCA[i][j] =
          lca(intervalLCA[i][j - 1], intervalLCA[i + (1 << (j - 1))][j - 1]);
    }
  }
}
int queryMin(int l, int r) {
  int d = (int)(log(r - l + 1) / log(2.0));
  int u = rmin[l][d];
  int v = rmin[r - (1 << d) + 1][d];
  if (eulerIndex[u] > eulerIndex[v]) return v;
  return u;
}
int queryMax(int l, int r) {
  int d = (int)(log(r - l + 1) / log(2.0));
  int u = rmax[l][d];
  int v = rmax[r - (1 << d) + 1][d];
  if (eulerIndex[u] > eulerIndex[v]) return u;
  return v;
}
int queryLCA(int l, int r) {
  int d = (int)(log(r - l + 1) / log(2.0));
  return lca(intervalLCA[l][d], intervalLCA[r - (1 << d) + 1][d]);
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> q;
  for (int i = 2; i <= n; i++) {
    int p;
    cin >> p;
    g[p].push_back(i);
    g[i].push_back(p);
    par[i][0] = p;
  }
  par[1][0] = 1;
  for (int j = 1; j < L; j++) {
    for (int i = 1; i <= n; i++) {
      par[i][j] = par[par[i][j - 1]][j - 1];
    }
  }
  lvl[0] = -1;
  dfs(1, 0);
  buildSparseTables();
  for (int qq = 1; qq <= q; qq++) {
    int l, r;
    cin >> l >> r;
    int qmx = queryMax(l, r);
    int qmn = queryMin(l, r);
    int torem = qmx, qans = 1, tmpans;
    if (qmx == l || qmx == r) {
      qans = lvl[queryLCA(qmx == l ? l + 1 : l, qmx == r ? r - 1 : r)];
    } else {
      qans = lvl[lca(queryLCA(l, qmx - 1), queryLCA(qmx + 1, r))];
    }
    if (qmn == l || qmn == r) {
      tmpans = lvl[queryLCA(qmn == l ? l + 1 : l, qmn == r ? r - 1 : r)];
    } else {
      tmpans = lvl[lca(queryLCA(l, qmn - 1), queryLCA(qmn + 1, r))];
    }
    if (tmpans > qans) {
      torem = qmn;
      qans = tmpans;
    }
    cout << torem << " " << qans << endl;
  }
  return 0;
}
