#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, LOG = 22;
int n, q, tin[N], tout[N], P[N][LOG], h[N], dfsTime;
vector<int> adj[N];
struct SegmentTree {
  int n;
  vector<pair<int, int> > st;
  SegmentTree() {}
  SegmentTree(int _n) {
    this->n = _n;
    st.assign(4 * n + 5, {0, 0});
  }
  int Left(int x) { return (x << 1); }
  int Right(int x) { return (x << 1) + 1; }
  void update(int id, int L, int R, int i, int val) {
    if (L > i || R < i) return;
    if (L == R) {
      st[id] = {val, i};
      return;
    }
    int mid = (L + R) >> 1;
    update(Left(id), L, mid, i, val);
    update(Right(id), mid + 1, R, i, val);
    st[id] = max(st[Left(id)], st[Right(id)]);
  }
  pair<int, int> query(int id, int L, int R, int i, int j) {
    if (L > j || R < i) return {-5 * N, 0};
    if (L >= i && R <= j) return st[id];
    int mid = (L + R) >> 1;
    return max(query(Left(id), L, mid, i, j),
               query(Right(id), mid + 1, R, i, j));
  }
  void update(int val, int i) { update(1, 1, n, i, val); }
  pair<int, int> query(int i, int j) { return query(1, 1, n, i, j); }
} IT1, IT2;
void dfs(int u, int pre) {
  if (~pre) h[u] = h[pre] + 1;
  P[u][0] = pre;
  tin[u] = ++dfsTime;
  for (int i = 1; i < LOG; ++i)
    if ((1 << i) <= h[u]) P[u][i] = P[P[u][i - 1]][i - 1];
  for (int v : adj[u]) dfs(v, u);
  tout[u] = ++dfsTime;
}
int lca(int u, int v) {
  if (u == -1) return v;
  if (v == -1) return u;
  if (h[u] < h[v]) swap(u, v);
  for (int i = LOG - 1; i >= 0; --i)
    if ((1 << i) <= h[u] - h[v]) {
      u = P[u][i];
    }
  if (u == v) return u;
  for (int i = LOG - 1; i >= 0; --i)
    if ((1 << i) <= h[u] && P[u][i] != P[v][i]) u = P[u][i], v = P[v][i];
  return P[u][0];
}
int fullsolve(int l, int r, int x) {
  if (l > r) return -1;
  int mi = -IT1.query(l, r).first, mx = IT2.query(l, r).first;
  int nb = (int)log2(h[x]), cur = 0, curV = x;
  if (tin[x] <= mi && tout[x] >= mx) return x;
  for (int i = nb; i >= 0; --i)
    if ((1 << i) <= h[curV]) {
      int tmp = P[curV][i];
      if (tin[tmp] <= mi && tout[tmp] >= mx) continue;
      curV = tmp;
      cur += (1 << i);
    }
  return (curV == 1 ? 1 : P[curV][0]);
}
int main(int argc, char const *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> q;
  for (int i = 2; i <= n; ++i) {
    int p;
    cin >> p;
    adj[p].push_back(i);
  }
  dfs(1, -1);
  IT1 = SegmentTree(n), IT2 = SegmentTree(n);
  for (int i = 1; i <= n; ++i) {
    IT1.update(-tin[i], i);
    IT2.update(tout[i], i);
  }
  while (q--) {
    int l, r;
    cin >> l >> r;
    int id1 = IT1.query(l, r).second;
    int pillar = l;
    if (id1 == l) pillar++;
    int a1 = lca(fullsolve(l, id1 - 1, pillar), fullsolve(id1 + 1, r, id1 + 1));
    int id2 = IT2.query(l, r).second;
    pillar = l;
    if (id2 == l) pillar++;
    int a2 = lca(fullsolve(id2 + 1, r, id2 + 1), fullsolve(l, id2 - 1, pillar));
    if (h[a1] > h[a2]) {
      cout << id1 << ' ' << h[a1] << endl;
    } else
      cout << id2 << ' ' << h[a2] << endl;
  }
  return 0;
}
