#include <bits/stdc++.h>
using namespace std;
mt19937 ran(time(0));
int mod = 1e9 + 7;
long long Bpow(long long a, long long s) {
  if (s == 0) {
    return 1;
  }
  long long u = Bpow(a, s / 2);
  if (s & 1)
    return u * u % mod * a % mod;
  else
    return u * u % mod;
}
vector<vector<int>> g(1e5 + 7);
vector<vector<int>> p(1e5 + 7, vector<int>(20));
vector<int> tin(1e5 + 7);
vector<int> tout(1e5 + 7);
vector<int> H(1e5 + 7);
int tcur = 0;
int n, q;
void dfs(int v, int par = -1, int h = 0) {
  if (par != -1) {
    p[v][0] = par;
    for (int i = 1; i < 20; i++) {
      p[v][i] = p[p[v][i - 1]][i - 1];
    }
  }
  H[v] = h;
  tin[v] = tcur++;
  for (auto& to : g[v]) {
    if (to != par) dfs(to, v, h + 1);
  }
  tout[v] = tcur++;
}
int k;
vector<pair<int, int>> mitin(1e6 + 8);
vector<pair<int, int>> matout(1e6 + 7);
int S(int n) {
  int ans = 1;
  while (ans < n) ans <<= 1;
  return ans;
}
pair<int, int> getmin(int l, int r) {
  pair<int, int> ans = {1e9 + 7, 1e9 + 7};
  for (l += k, r += k; l <= r; l >>= 1, r >>= 1) {
    if (l & 1) {
      ans = min(ans, mitin[l++]);
    }
    if (~r & 1) {
      ans = min(ans, mitin[r--]);
    }
  }
  return ans;
}
pair<int, int> getmax(int l, int r) {
  pair<int, int> ans = {0, 0};
  for (l += k, r += k; l <= r; l >>= 1, r >>= 1) {
    if (l & 1) {
      ans = max(ans, matout[l++]);
    }
    if (~r & 1) {
      ans = max(ans, matout[r--]);
    }
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie();
  cin >> n >> q;
  for (int i = 2; i < n + 1; i++) {
    int a;
    cin >> a;
    g[a].push_back(i);
    g[i].push_back(a);
  }
  dfs(1);
  k = S(n);
  for (int i = 1; i < n + 1; i++) {
    mitin[i + k - 1] = {tin[i], i};
    matout[i + k - 1] = {tout[i], i};
  }
  for (int i = k - 1; i > 0; i--) {
    mitin[i] = min(mitin[i * 2], mitin[i * 2 + 1]);
    matout[i] = max(matout[i * 2], matout[i * 2 + 1]);
  }
  while (q--) {
    int l, r;
    cin >> l >> r;
    --l, --r;
    pair<int, int> mit = getmin(l, r);
    pair<int, int> mat = getmax(l, r);
    pair<int, int> sec = max(getmax(l, mat.second - 2), getmax(mat.second, r));
    int nem = sec.first;
    int v = min(getmin(l, mat.second - 2), getmin(mat.second, r)).second;
    int now = 19;
    while (now >= 0) {
      if (p[v][now] && tout[p[v][now]] < nem) v = p[v][now];
      now--;
    }
    int h1;
    if (tout[v] >= nem)
      h1 = H[v];
    else
      h1 = H[p[v][0]];
    sec = min(getmin(l, mit.second - 2), getmin(mit.second, r));
    nem = sec.first;
    v = max(getmax(l, mit.second - 2), getmax(mit.second, r)).second;
    now = 19;
    while (now >= 0) {
      if (p[v][now] && tin[p[v][now]] > nem) v = p[v][now];
      now--;
    }
    int h2;
    if (tin[v] <= nem)
      h2 = H[v];
    else
      h2 = H[p[v][0]];
    if (h1 > h2) {
      cout << mat.second << " " << h1 << "\n";
    } else
      cout << mit.second << " " << h2 << "\n";
  }
}
