#include <bits/stdc++.h>
using namespace std;
template <typename T>
T read1() {
  T t = 0;
  char k;
  bool v = 0;
  do (k = getchar()) == '-' && (v = 1);
  while ('0' > k || k > '9');
  while ('0' <= k && k <= '9')
    t = (t << 3) + (t << 1) + (k ^ '0'), k = getchar();
  return v ? -t : t;
}
int s, dfn[100005][20][2], q, l2[200005], rk[200005];
vector<int> G[100005];
pair<int, int> h[200005][20];
void dfs(int n, int fa) {
  h[dfn[n][0][0] = dfn[n][0][1] = ++dfn[0][0][0]][0] =
      make_pair(h[dfn[fa][0][0]][0].first + 1, n);
  rk[dfn[n][0][0]] = n;
  for (int i = 0; i < G[n].size(); ++i)
    if (G[n][i] ^ fa)
      dfs(G[n][i], n), h[++dfn[0][0][0]][0] = h[dfn[n][0][0]][0],
                       rk[dfn[0][0][0]] = n;
}
void make() {
  for (int i = 1; (1 << i) <= dfn[0][0][0]; ++i)
    for (int j = 1; j + (1 << i) - 1 <= dfn[0][0][0]; ++j)
      h[j][i] = min(h[j][i - 1], h[j + (1 << i - 1)][i - 1]);
  for (int i = 1; (1 << i) <= s; ++i)
    for (int j = 1; j + (1 << i) - 1 <= s; ++j)
      dfn[j][i][0] = max(dfn[j][i - 1][0], dfn[j + (1 << i - 1)][i - 1][0]),
      dfn[j][i][1] = min(dfn[j][i - 1][1], dfn[j + (1 << i - 1)][i - 1][1]);
}
int query(int l, int r, int ty) {
  if (l > r) swap(l, r);
  int w = l2[r - l + 1], t = r - (1 << w) + 1;
  if (ty == 1) return min(h[l][w], h[t][w]).first;
  if (ty == 2) return max(dfn[l][w][0], dfn[t][w][0]);
  if (ty == 3) return min(dfn[l][w][1], dfn[t][w][1]);
  return min(h[l][w], h[t][w]).second;
}
int get(int l, int r, int w) {
  if (l == w) return query(query(w + 1, r, 3), query(w + 1, r, 2), 1);
  if (r == w) return query(query(l, w - 1, 3), query(l, w - 1, 2), 1);
  return query(dfn[query(query(l, w - 1, 3), query(l, w - 1, 2), 4)][0][0],
               dfn[query(query(w + 1, r, 3), query(w + 1, r, 2), 4)][0][0], 1);
}
int main() {
  s = read1<long long>(), q = read1<long long>();
  for (int i = 2; i <= s; ++i)
    G[i].push_back(read1<long long>()), G[G[i].back()].push_back(i);
  dfs(1, 0);
  make();
  for (int i = 2; i <= dfn[0][0][0]; ++i) l2[i] = l2[i >> 1] + 1;
  for (int i = 1; i <= q; ++i) {
    int l = read1<long long>(), r = read1<long long>(), o = query(l, r, 3),
        p = query(l, r, 2), x = get(l, r, rk[o]), y = get(l, r, rk[p]);
    if (x > y)
      printf("%d %d\n", rk[o], x - 1);
    else
      printf("%d %d\n", rk[p], y - 1);
  }
  return 0;
}
