#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;
template <typename Tp>
struct RMQ {
  int n;
  int len[MAXN];
  Tp mx[MAXN][21];
  Tp mi[MAXN][21];
  void build_rmq() {
    for (int j = 1; (1 << j) <= n; j++)
      for (int i = 1; i + (1 << j) - 1 <= n; i++) {
        mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
        mi[i][j] = min(mi[i][j - 1], mi[i + (1 << (j - 1))][j - 1]);
      }
  }
  int QueryMax(int L, int R) {
    if (L > R) return 0;
    int k = len[R - L + 1];
    return max(mx[L][k], mx[R - (1 << k) + 1][k]);
  }
  int QueryMin(int L, int R) {
    if (L > R) return INF;
    int k = len[R - L + 1];
    return min(mi[L][k], mi[R - (1 << k) + 1][k]);
  }
  void init(Tp *a, int sz) {
    n = sz;
    for (int i = 1; i <= n; i++) mx[i][0] = mi[i][0] = a[i];
    build_rmq();
    for (int i = 0; i <= n; i++) len[i] = (i == 0 ? -1 : len[i >> 1] + 1);
  }
};
RMQ<int> st;
int n, q, mx = 0, tim = 0;
vector<int> E[MAXN];
int in[MAXN], out[MAXN], pos[MAXN], dep[MAXN], fa[MAXN][20];
void dfs(int now, int f = 1, int dp = 0) {
  mx = max(mx, dp);
  fa[now][0] = f;
  for (int i = 1; i < 20; i++) fa[now][i] = fa[fa[now][i - 1]][i - 1];
  in[now] = ++tim;
  dep[now] = dp;
  pos[tim] = now;
  for (int v : E[now]) {
    dfs(v, now, dp + 1);
  }
  out[now] = tim;
}
int up(int L, int R, int now) {
  if (in[now] <= L && out[now] >= R) return dep[now];
  for (int i = 19; i >= 0; i--) {
    int f = fa[now][i];
    if (in[f] <= L && out[f] >= R) continue;
    now = fa[now][i];
  }
  return dep[fa[now][0]];
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 2; i <= n; i++) {
    int x;
    scanf("%d", &x);
    E[x].push_back(i);
  }
  dfs(1);
  st.init(in, n);
  for (int i = 1; i <= q; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    if (l == r) {
      printf("%d %d\n", l, mx);
    } else {
      int Mi = st.QueryMin(l, r);
      int Mx = st.QueryMax(l, r);
      int dep1, dep2;
      int now1, now2;
      int st1, st2;
      now1 = min(st.QueryMin(l, pos[Mi] - 1), st.QueryMin(pos[Mi] + 1, r));
      now2 = max(st.QueryMax(l, pos[Mx] - 1), st.QueryMax(pos[Mx] + 1, r));
      st1 = pos[Mx], st2 = pos[Mi];
      dep1 = up(now1, Mx, st1);
      dep2 = up(Mi, now2, st2);
      if (dep1 > dep2)
        printf("%d %d\n", st2, dep1);
      else
        printf("%d %d\n", st1, dep2);
    }
  }
  return 0;
}
