#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 2;
int n, q, dep[N];
int tin[N], tout[N], timer, p[20][N];
vector<int> g[N];
pair<int, int> t[N * 4], mx[N * 4];
void dfs(int v, int pr = 0) {
  tin[v] = ++timer;
  p[0][v] = pr;
  for (int i = 1; i < 20; i++) p[i][v] = p[i - 1][p[i - 1][v]];
  for (int to : g[v]) {
    if (to == pr) continue;
    dep[to] = dep[v] + 1;
    dfs(to, v);
  }
  tout[v] = timer;
}
int upper(int a, int b) { return tin[a] <= tin[b] && tout[a] >= tout[b]; }
int lca(int a, int b) {
  if (upper(a, b)) return a;
  if (upper(b, a)) return b;
  for (int i = 19; i >= 0; i--) {
    if (p[i][a] && !upper(p[i][a], b)) a = p[i][a];
  }
  return p[0][a];
}
void build(int v = 1, int tl = 1, int tr = n) {
  if (tl == tr) {
    t[v] = {tin[tl], tl};
    mx[v] = {tin[tl], tl};
  } else {
    int tm = (tl + tr) >> 1;
    build(v << 1, tl, tm);
    build((v << 1) | 1, tm + 1, tr);
    t[v] = min(t[v << 1], t[(v << 1) | 1]);
    mx[v] = max(mx[v << 1], mx[(v << 1) | 1]);
  }
}
pair<int, int> get(int l, int r, int v = 1, int tl = 1, int tr = n) {
  if (l > tr || tl > r) return {1e9, 1e9};
  if (l <= tl && tr <= r) return t[v];
  int tm = (tl + tr) >> 1;
  return min(get(l, r, v << 1, tl, tm), get(l, r, (v << 1) | 1, tm + 1, tr));
}
pair<int, int> getm(int l, int r, int v = 1, int tl = 1, int tr = n) {
  if (l > tr || tl > r) return {0, 0};
  if (l <= tl && tr <= r) return mx[v];
  int tm = (tl + tr) >> 1;
  return max(getm(l, r, v << 1, tl, tm), getm(l, r, (v << 1) | 1, tm + 1, tr));
}
int getlca(int l, int r) {
  pair<int, int> mx = get(l, r), mn = getm(l, r);
  return lca(mx.second, mn.second);
}
int main() {
  cin >> n >> q;
  for (int i = 2; i <= n; i++) {
    int p;
    cin >> p;
    g[i].push_back(p);
    g[p].push_back(i);
  }
  dfs(1);
  build();
  while (q--) {
    int l, r;
    cin >> l >> r;
    pair<int, int> m1 = get(l, r);
    pair<int, int> m2 = getm(l, r);
    int l1, l2;
    if (m1.second > l) {
      l1 = getlca(l, m1.second - 1);
      if (m1.second < r) {
        l1 = lca(l1, getlca(m1.second + 1, r));
      }
    } else {
      l1 = getlca(m1.second + 1, r);
    }
    if (m2.second > l) {
      l2 = getlca(l, m2.second - 1);
      if (m2.second < r) {
        l2 = lca(l2, getlca(m2.second + 1, r));
      }
    } else {
      l2 = getlca(m2.second + 1, r);
    }
    if (dep[l1] < dep[l2]) {
      cout << m2.second << " " << dep[l2] << endl;
    } else {
      cout << m1.second << " " << dep[l1] << endl;
    }
  }
}
