#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];
}
struct node {
  int M, m;
  node() {}
  node(int a, int b) : M(a), m(b) {}
} seg[100000 + 5][18];
int mymax(int x, int y) { return fi[x] > fi[y] ? x : y; }
int mymin(int x, int y) { return fi[x] < fi[y] ? x : y; }
node Merge(node a, node b) { return node(mymax(a.M, b.M), mymin(a.m, b.m)); }
int mm, MM;
node ASK(int l, int r) {
  if (l > r) return node(mm, MM);
  int k = lg[r - l + 1];
  return Merge(seg[l][k], seg[r - (1 << k) + 1][k]);
}
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];
  for (int i = 1; i <= n; i++) seg[i][0] = node(i, i);
  for (int i = 1; i <= 16; i++)
    for (int j = 1; j <= n; j++)
      seg[j][i] = Merge(seg[j][i - 1], seg[j + (1 << i - 1)][i - 1]);
  fi[mm = n + 1] = -0x3f3f3f3f;
  fi[MM = n + 2] = 0x3f3f3f3f;
  while (q--) {
    int l, r;
    scanf("%d%d", &l, &r);
    node tmp = ASK(l, r);
    node t1 = Merge(ASK(l, tmp.M - 1), ASK(tmp.M + 1, r));
    node t2 = Merge(ASK(l, tmp.m - 1), ASK(tmp.m + 1, r));
    int ansM = dep[ask(fi[t1.m], fi[t1.M])];
    int ansm = dep[ask(fi[t2.m], fi[t2.M])];
    if (ansM > ansm)
      printf("%d %d\n", tmp.M, ansM);
    else
      printf("%d %d\n", tmp.m, ansm);
  }
  return 0;
}
