#include <bits/stdc++.h>
const int maxn = 1e5 + 10, mod = 1e9 + 7;
using namespace std;
int n, m, k, t;
int tot;
vector<int> e[maxn];
int dfn[maxn];
int fa[20][maxn];
int mi[20][maxn], ma[20][maxn];
int pa[20][maxn];
int dep[maxn];
int p[maxn];
void dfs(int x, int y = 1) {
  dfn[x] = ++tot;
  dep[x] = y;
  for (int i = 1; fa[i - 1][fa[i - 1][x]]; i++) {
    fa[i][x] = fa[i - 1][fa[i - 1][x]];
  }
  for (auto z : e[x]) {
    fa[0][z] = x;
    dfs(z, y + 1);
  }
}
int lca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  for (int i = 19; i >= 0; i--) {
    if (dep[fa[i][x]] >= dep[y]) {
      x = fa[i][x];
    }
  }
  if (x == y) return x;
  for (int i = 19; i >= 0; i--) {
    if (fa[i][x] != fa[i][y]) {
      x = fa[i][x], y = fa[i][y];
    }
  }
  return fa[0][x];
}
void init_rmq() {
  for (int i = 1; i <= n; i++) mi[0][i] = ma[0][i] = pa[0][i] = i;
  for (int i = 1; 1 << i <= n; i++) {
    for (int j = 1; j + (1 << i) - 1 <= n; j++) {
      int x = mi[i - 1][j], y = mi[i - 1][j + (1 << (i - 1))];
      if (dfn[x] < dfn[y])
        mi[i][j] = x;
      else
        mi[i][j] = y;
      x = ma[i - 1][j], y = ma[i - 1][j + (1 << (i - 1))];
      if (dfn[x] > dfn[y])
        ma[i][j] = x;
      else
        ma[i][j] = y;
      x = pa[i - 1][j], y = pa[i - 1][j + (1 << (i - 1))];
      pa[i][j] = lca(x, y);
    }
  }
}
int query_min_dfn(int l, int r) {
  int x = p[r - l + 1];
  int y = mi[x][l], z = mi[x][r - (1 << x) + 1];
  if (dfn[y] < dfn[z]) return y;
  return z;
}
int query_max_dfn(int l, int r) {
  int x = p[r - l + 1];
  int y = ma[x][l], z = ma[x][r - (1 << x) + 1];
  if (dfn[y] > dfn[z]) return y;
  return z;
}
int query_lca(int l, int r) {
  int x = p[r - l + 1];
  int y = pa[x][l], z = pa[x][r - (1 << x) + 1];
  return lca(y, z);
}
int main() {
  int i, j;
  scanf("%d%d", &n, &m);
  for (i = 2; i <= n; i++) {
    scanf("%d", &j);
    e[j].push_back(i);
    p[i] = 1 + p[i >> 1];
  }
  dfs(1);
  init_rmq();
  for (i = 1; i <= m; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    int x = query_min_dfn(l, r), pa = -1;
    if (l < x) pa = query_lca(l, x - 1);
    if (r > x) {
      if (!~pa)
        pa = query_lca(x + 1, r);
      else
        pa = lca(pa, query_lca(x + 1, r));
    }
    int y = query_max_dfn(l, r), pb = -1;
    if (l < y) pb = query_lca(l, y - 1);
    if (r > y) {
      if (!~pb)
        pb = query_lca(y + 1, r);
      else
        pb = lca(pb, query_lca(y + 1, r));
    }
    if (dep[pa] > dep[pb]) {
      printf("%d %d\n", x, dep[pa] - 1);
    } else
      printf("%d %d\n", y, dep[pb] - 1);
  }
  return 0;
}
