#include <bits/stdc++.h>
using namespace std;
vector<int> e[100000 + 5];
int dep[100000 + 5], euler[100000 * 2 + 5], fi[100000 + 5], cnt;
void dfs(int now) {
  euler[++cnt] = now;
  fi[now] = cnt;
  for (auto v : e[now]) {
    dep[v] = dep[now] + 1;
    dfs(v);
    euler[++cnt] = now;
  }
  return;
}
int lg[100000 * 2 + 5], st[100000 * 2 + 5][18];
int ask(int l, int r) {
  int k = lg[r - l + 1];
  return dep[st[l][k]] < dep[st[r - (1 << k) + 1][k]] ? st[l][k]
                                                      : st[r - (1 << k) + 1][k];
}
int cmp(int x, int y) {
  if (fi[x] < fi[y]) return -1;
  if (fi[x] > fi[y]) return 1;
  return 0;
}
struct node {
  int l, r;
  int M[2], m[2];
} t[100000 * 4 + 5];
int a[100000 + 5];
void pushup(int i) {
  if (cmp(t[i * 2].M[0], t[i * 2 + 1].M[0]) == 1) {
    t[i].M[0] = t[i * 2].M[0];
    if (cmp(t[i * 2].M[1], t[i * 2 + 1].M[0]) == 1)
      t[i].M[1] = t[i * 2].M[1];
    else
      t[i].M[1] = t[i * 2 + 1].M[0];
  } else {
    t[i].M[0] = t[i * 2 + 1].M[0];
    if (cmp(t[i * 2 + 1].M[1], t[i * 2].M[0]) == 1)
      t[i].M[1] = t[i * 2 + 1].M[1];
    else
      t[i].M[1] = t[i * 2].M[0];
  }
  if (cmp(t[i * 2].m[0], t[i * 2 + 1].m[0]) == -1) {
    t[i].m[0] = t[i * 2].m[0];
    if (cmp(t[i * 2].m[1], t[i * 2 + 1].m[0]) == -1)
      t[i].m[1] = t[i * 2].m[1];
    else
      t[i].m[1] = t[i * 2 + 1].m[0];
  } else {
    t[i].m[0] = t[i * 2 + 1].m[0];
    if (cmp(t[i * 2 + 1].m[1], t[i * 2].m[0]) == -1)
      t[i].m[1] = t[i * 2 + 1].m[1];
    else
      t[i].m[1] = t[i * 2].m[0];
  }
}
int _Mid, _mid;
void build(int i, int l, int r) {
  t[i].l = l;
  t[i].r = r;
  if (l == r) {
    t[i].M[0] = t[i].m[0] = l;
    t[i].M[1] = _mid;
    t[i].m[1] = _Mid;
  } else {
    build(i * 2, l, (r + l) / 2);
    build(i * 2 + 1, (r + l) / 2 + 1, r);
    pushup(i);
  }
  return;
}
int M[2], m[2];
void query(int i, int l, int r) {
  if (r < t[i].l || t[i].r < l) return;
  if (l <= t[i].l && t[i].r <= r) {
    if (cmp(M[0], t[i].M[0]) == 1) {
      if (cmp(M[1], t[i].M[0]) == -1) M[1] = t[i].M[0];
    } else {
      M[1] = M[0];
      M[0] = t[i].M[0];
      if (cmp(M[1], t[i].M[1]) == -1) M[1] = t[i].M[1];
    }
    if (cmp(m[0], t[i].m[0]) == -1) {
      if (cmp(m[1], t[i].m[0]) == 1) m[1] = t[i].m[0];
    } else {
      m[1] = m[0];
      m[0] = t[i].m[0];
      if (cmp(m[1], t[i].m[1]) == 1) m[1] = t[i].m[1];
    }
    return;
  }
  query(i * 2, l, r);
  query(i * 2 + 1, l, r);
}
int main() {
  lg[1] = 0;
  for (int i = 2; i <= 100000 * 2; i++) lg[i] = lg[i >> 1] + 1;
  int n, q;
  scanf("%d%d", &n, &q);
  for (int i = 2; i <= n; i++) {
    int x;
    scanf("%d", &x);
    e[x].push_back(i);
  }
  dfs(1);
  int N = n * 2 - 1;
  for (int i = 1; i <= N; i++) st[i][0] = euler[i];
  for (int i = 1; i <= lg[N]; i++)
    for (int j = 1; j <= N - (1 << i) + 1; j++)
      st[j][i] = dep[st[j][i - 1]] < dep[st[j + (1 << i - 1)][i - 1]]
                     ? st[j][i - 1]
                     : st[j + (1 << i - 1)][i - 1];
  fi[n + 1] = -0x3f3f3f3f;
  fi[n + 2] = 0x3f3f3f3f;
  _mid = n + 1;
  _Mid = n + 2;
  build(1, 1, n);
  while (q--) {
    int l, r;
    scanf("%d%d", &l, &r);
    M[0] = M[1] = _mid;
    m[0] = m[1] = _Mid;
    query(1, l, r);
    if (dep[ask(fi[m[0]], fi[M[1]])] > dep[ask(fi[m[1]], fi[M[0]])])
      printf("%d %d\n", M[0], dep[ask(fi[m[0]], fi[M[1]])]);
    else
      printf("%d %d\n", m[0], dep[ask(fi[m[1]], fi[M[0]])]);
  }
  return 0;
}
