#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 10;
const long long mod = 1e9 + 7;
int n, q;
int a[N], clk, id[N], fa[N];
vector<int> G[N];
int siz[N], son[N], topf[N], dep[N];
void dfs(int u) {
  siz[u] = 1;
  for (int v : G[u]) {
    dep[v] = dep[u] + 1;
    dfs(v);
    siz[u] += siz[v];
    if (siz[v] > siz[son[u]]) son[u] = v;
  }
}
void dfs2(int u, int topfa) {
  topf[u] = topfa;
  a[u] = ++clk;
  id[clk] = u;
  if (!son[u]) return;
  dfs2(son[u], topfa);
  for (int v : G[u]) {
    if (!topf[v]) dfs2(v, v);
  }
}
int LCA(int u, int v) {
  while (topf[u] ^ topf[v]) {
    dep[topf[u]] < dep[topf[v]] ? v = fa[topf[v]] : u = fa[topf[u]];
  }
  return dep[u] < dep[v] ? u : v;
}
int mx[N << 2], mn[N << 2];
void up(int rt) {
  mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
  mn[rt] = min(mn[rt << 1], mn[rt << 1 | 1]);
}
void build(int l, int r, int rt) {
  if (l == r) {
    mn[rt] = mx[rt] = a[l];
    return;
  }
  build(l, ((l + r) >> 1), rt << 1);
  build(((l + r) >> 1) + 1, r, rt << 1 | 1);
  up(rt);
}
void cg(int q, int x, int l, int r, int rt) {
  if (l == r) {
    if (x == -1) {
      mn[rt] = INF;
      mx[rt] = 0;
    } else
      mn[rt] = mx[rt] = x;
    return;
  }
  if (q <= ((l + r) >> 1))
    cg(q, x, l, ((l + r) >> 1), rt << 1);
  else
    cg(q, x, ((l + r) >> 1) + 1, r, rt << 1 | 1);
  up(rt);
}
int qrymn(int ql, int qr, int l, int r, int rt) {
  if (ql <= l && qr >= r) return mn[rt];
  int res = INF;
  if (ql <= ((l + r) >> 1))
    res = min(res, qrymn(ql, qr, l, ((l + r) >> 1), rt << 1));
  if (qr > ((l + r) >> 1))
    res = min(res, qrymn(ql, qr, ((l + r) >> 1) + 1, r, rt << 1 | 1));
  return res;
}
int qrymx(int ql, int qr, int l, int r, int rt) {
  if (ql <= l && qr >= r) return mx[rt];
  int res = 0;
  if (ql <= ((l + r) >> 1))
    res = max(res, qrymx(ql, qr, l, ((l + r) >> 1), rt << 1));
  if (qr > ((l + r) >> 1))
    res = max(res, qrymx(ql, qr, ((l + r) >> 1) + 1, r, rt << 1 | 1));
  return res;
}
int main() {
  scanf("%d%d", &n, &q);
  memset(mn, 0x3f, sizeof(mn));
  memset(mx, 0, sizeof(mx));
  for (int i = 2; i <= n; i++) {
    scanf("%d", &fa[i]);
    G[fa[i]].push_back(i);
  }
  dfs(1);
  dfs2(1, 1);
  build(1, n, 1);
  while (q--) {
    int l, r;
    scanf("%d%d", &l, &r);
    int x = id[qrymn(l, r, 1, n, 1)], y = id[qrymx(l, r, 1, n, 1)];
    if (r == l + 1) {
      if (dep[x] >= dep[y])
        printf("%d %d\n", y, dep[x]);
      else
        printf("%d %d\n", x, dep[y]);
    } else {
      cg(x, -1, 1, n, 1);
      int tx = id[qrymn(l, r, 1, n, 1)];
      int lca1 = LCA(tx, y);
      cg(x, a[x], 1, n, 1);
      cg(y, -1, 1, n, 1);
      int ty = id[qrymx(l, r, 1, n, 1)];
      int lca2 = LCA(x, ty);
      cg(y, a[y], 1, n, 1);
      if (dep[lca1] > dep[lca2]) {
        printf("%d %d\n", x, dep[lca1]);
      } else {
        printf("%d %d\n", y, dep[lca2]);
      }
    }
  }
  return 0;
}
