#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int t[N], d[N], ind, n, testcase, q[N][20], par[N][20], h[N];
vector<int> a[N];
struct two {
  int mi, ma;
};
two st[4 * N];
void dfs(int u, int p) {
  t[u] = ++ind;
  d[ind] = u;
  for (int v : a[u])
    if (v != p) {
      h[v] = h[u] + 1;
      q[v][0] = u;
      dfs(v, u);
    }
}
void initLCA() {
  for (int j = 1; j <= log2(n); j++) {
    for (int i = 1; i <= n; i++) q[i][j] = q[q[i][j - 1]][j - 1];
  }
}
int LCA(int u, int v) {
  if (h[u] < h[v]) swap(u, v);
  if (u == 0 || v == 0) return u + v;
  int k = log2(h[u]);
  for (int i = k; i >= 0; i--)
    if (h[u] - (1 << i) >= h[v]) u = q[u][i];
  if (u == v) return u;
  for (int i = k; i >= 0; i--)
    if (q[u][i] && q[u][i] != q[v][i]) {
      u = q[u][i];
      v = q[v][i];
    }
  return q[u][0];
}
void initRMQ() {
  for (int i = 1; i <= n; i++) par[i][0] = i;
  for (int j = 1; j <= log2(n); j++) {
    for (int i = 1; i <= n; i++)
      par[i][j] = LCA(par[i][j - 1], par[i + (1 << (j - 1))][j - 1]);
  }
}
two up(two A, two B) {
  two k;
  k.mi = min(A.mi, B.mi);
  k.ma = max(A.ma, B.ma);
  return k;
}
void build(int i, int l, int r) {
  if (l == r) {
    st[i].mi = st[i].ma = t[l];
    return;
  }
  build(i * 2, l, (l + r) / 2);
  build(i * 2 + 1, (l + r) / 2 + 1, r);
  st[i] = up(st[2 * i], st[2 * i + 1]);
}
two get(int i, int l, int r, int u, int v) {
  if (u > r || v < l) return {1000000000, -1};
  if (u <= l && r <= v) return st[i];
  return up(get(i * 2, l, (l + r) / 2, u, v),
            get(i * 2 + 1, (l + r) / 2 + 1, r, u, v));
}
int get_(int i, int j) {
  if (i > j) return 0;
  int k = log2(j - i + 1);
  return LCA(par[i][k], par[j - (1 << k) + 1][k]);
}
void create() {
  dfs(1, 1);
  initLCA();
  initRMQ();
  build(1, 1, n);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> testcase;
  for (int i = 2; i <= n; i++) {
    int x;
    cin >> x;
    a[x].push_back(i);
  }
  create();
  while (testcase--) {
    int l, r;
    cin >> l >> r;
    two tmp = get(1, 1, n, l, r);
    int p1 = d[tmp.mi];
    int p2 = d[tmp.ma];
    int u = get_(l, p1 - 1);
    int v = get_(p1 + 1, r);
    int k1 = LCA(u, v);
    u = get_(l, p2 - 1);
    v = get_(p2 + 1, r);
    int k2 = LCA(u, v);
    u = k1;
    v = k2;
    if (h[u] > h[v])
      cout << p1 << ' ' << h[u] << '\n';
    else
      cout << p2 << ' ' << h[v] << '\n';
  }
}
