#include <bits/stdc++.h>
using namespace std;
int n, q, f[100005][20 + 5], dep[100005], dfn[100005], cnt, res[100005];
vector<int> G[100005];
struct node {
  int l, r, mi, mx;
} tree[100005 * 4];
void pushmx(int Index) {
  tree[Index].mx = max(tree[Index * 2].mx, tree[Index * 2 + 1].mx);
}
void pushmi(int Index) {
  tree[Index].mi = min(tree[Index * 2].mi, tree[Index * 2 + 1].mi);
}
void build(int Index, int l, int r) {
  tree[Index].l = l;
  tree[Index].r = r;
  tree[Index].mi = 0x3f3f3f3f;
  tree[Index].mx = 0;
  if (l == r) {
    tree[Index].mi = tree[Index].mx = dfn[l];
    return;
  }
  int mid = l + r >> 1;
  build(Index * 2, l, mid);
  build(Index * 2 + 1, mid + 1, r);
  pushmx(Index);
  pushmi(Index);
}
int query_mx(int Index, int l, int r) {
  if (tree[Index].l >= l && tree[Index].r <= r) return tree[Index].mx;
  int maxn = 0;
  int mid = (tree[Index].l + tree[Index].r) / 2;
  if (l <= mid) maxn = max(maxn, query_mx(Index * 2, l, r));
  if (r > mid) maxn = max(maxn, query_mx(Index * 2 + 1, l, r));
  return maxn;
}
int query_mi(int Index, int l, int r) {
  if (tree[Index].l >= l && tree[Index].r <= r) return tree[Index].mi;
  int minn = 0x3f3f3f3f;
  int mid = (tree[Index].l + tree[Index].r) / 2;
  if (l <= mid) minn = min(minn, query_mi(Index * 2, l, r));
  if (r > mid) minn = min(minn, query_mi(Index * 2 + 1, l, r));
  return minn;
}
void dfs(int x, int fa) {
  cnt++;
  dfn[x] = cnt;
  res[cnt] = x;
  dep[x] = dep[fa] + 1;
  for (int i = 0; i < G[x].size(); i++) {
    int tmp = G[x][i];
    f[tmp][0] = x;
    dfs(tmp, x);
  }
}
void prepare() {
  for (int j = 1; j <= 20; j++)
    for (int i = 1; i <= n; i++) f[i][j] = f[f[i][j - 1]][j - 1];
}
void add(int &x, int maxdep) {
  for (int i = 20; i >= 0; i--)
    if (dep[f[x][i]] >= maxdep) x = f[x][i];
}
int Doubly(int x, int y) {
  if (dep[x] > dep[y]) add(x, dep[y]);
  if (dep[x] < dep[y]) add(y, dep[x]);
  if (x == y) return x;
  for (int i = 20; i >= 0; i--) {
    if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
  }
  return f[x][0];
}
int main() {
  scanf("%d %d", &n, &q);
  for (int i = 2; i <= n; i++) {
    int p;
    scanf("%d", &p);
    G[p].push_back(i);
  }
  dfs(1, 0);
  prepare();
  build(1, 1, n);
  while (q--) {
    int l, r, L1, R1, L2, R2, ans1, ans2;
    scanf("%d %d", &l, &r);
    L1 = res[query_mi(1, l, r)];
    R1 = res[query_mx(1, l, r)];
    L2 = res[min(query_mi(1, l, L1 - 1), query_mi(1, L1 + 1, r))];
    R2 = res[max(query_mx(1, l, R1 - 1), query_mx(1, R1 + 1, r))];
    ans1 = Doubly(L2, R1), ans2 = Doubly(L1, R2);
    if (dep[ans1] > dep[ans2])
      printf("%d %d\n", L1, dep[ans1] - 1);
    else
      printf("%d %d\n", R1, dep[ans2] - 1);
  }
  return 0;
}
