#include <bits/stdc++.h>
using namespace std;
int n, q;
vector<int> G[100055];
int id, ind[100055], fid[100055], dep[100055], fa[100055][22];
void dfs(int u, int pre) {
  ind[u] = ++id;
  fid[id] = u;
  fa[u][0] = pre;
  for (int j = 1; j <= 20; ++j) fa[u][j] = fa[fa[u][j - 1]][j - 1];
  for (int i = 0; i < G[u].size(); ++i) {
    int v = G[u][i];
    dep[v] = dep[u] + 1;
    dfs(v, u);
  }
}
int mx[100055][22], mn[100055][22], Log[100055];
void init_rmq() {
  Log[1] = 0;
  for (int i = 2; i <= n; ++i) Log[i] = Log[i >> 1] + 1;
  for (int i = 1; i <= n; ++i) mx[i][0] = mn[i][0] = ind[i];
  for (int i = 1; i <= 20; ++i) {
    for (int j = 1; j + (1 << (i - 1)) <= n; ++j) {
      mx[j][i] = max(mx[j][i - 1], mx[j + (1 << (i - 1))][i - 1]);
      mn[j][i] = min(mn[j][i - 1], mn[j + (1 << (i - 1))][i - 1]);
    }
  }
}
int ask_mn(int l, int r) {
  int L = Log[r - l + 1];
  return min(mn[l][L], mn[r - (1 << L) + 1][L]);
}
int ask_mx(int l, int r) {
  int L = Log[r - l + 1];
  return max(mx[l][L], mx[r - (1 << L) + 1][L]);
}
int lca(int u, int v) {
  if (dep[u] > dep[v]) swap(u, v);
  int tx = u, ty = v;
  for (int d = dep[v] - dep[u], i = 0; d; d >>= 1, ++i)
    if (d & 1) {
      ty = fa[ty][i];
    }
  if (tx == ty) return tx;
  for (int i = 20; i >= 0; --i) {
    if (fa[tx][i] == fa[ty][i]) continue;
    tx = fa[tx][i], ty = fa[ty][i];
  }
  return fa[tx][0];
}
int fd_fa(int x, int l, int r) {
  int u1, v1;
  if (x == l) {
    u1 = ask_mn(l + 1, r);
    v1 = ask_mx(l + 1, r);
  } else if (x == r) {
    u1 = ask_mn(l, r - 1);
    v1 = ask_mx(l, r - 1);
  } else {
    u1 = min(ask_mn(l, x - 1), ask_mn(x + 1, r));
    v1 = max(ask_mx(l, x - 1), ask_mx(x + 1, r));
  }
  return lca(fid[u1], fid[v1]);
}
int del(int x, int l, int r) {
  int p = l, ff;
  if (x == l)
    ff = r;
  else if (x == r)
    ff = l;
  else
    ff = l;
  for (int i = l; i <= r; ++i)
    if (i != x) {
      ff = lca(i, ff);
    }
  return dep[ff];
}
int main() {
  srand(time(0));
  scanf("%d%d", &n, &q);
  for (int p, i = 2; i <= n; ++i) scanf("%d", &p), G[p].push_back(i);
  dfs(1, 0);
  init_rmq();
  while (q--) {
    int l, r;
    scanf("%d%d", &l, &r);
    if (n == 2) {
      printf("1 1\n");
      continue;
    }
    int ld = ask_mn(l, r), rd = ask_mx(l, r);
    int fa1 = fd_fa(fid[ld], l, r), fa2 = fd_fa(fid[rd], l, r);
    if (dep[fa1] >= dep[fa2])
      printf("%d %d\n", fid[ld], dep[fa1]);
    else
      printf("%d %d\n", fid[rd], dep[fa2]);
  }
  return 0;
}
