#include <bits/stdc++.h>
using namespace std;
struct Edge {
  int to, next;
};
Edge E[200005];
int head[100005], Ecou;
int N, Q;
int dep[100005], fa[100005][19];
void init() {
  Ecou = 0;
  memset(head, -1, sizeof(head));
}
inline void addEdge(int u, int v) {
  E[Ecou].to = v;
  E[Ecou].next = head[u];
  head[u] = Ecou++;
}
void dfs(int u, int d) {
  for (int i = 1; i < 19; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
  dep[u] = d;
  for (int i = head[u]; i != -1; i = E[i].next) dfs(E[i].to, d + 1);
}
struct Node {
  int quan;
  vector<pair<int, int> > shao;
};
Node shao[100005][19];
size_t MMMM = 0;
inline int lca(int a, int b) {
  if (a == -1) return b;
  if (b == -1) return a;
  if (dep[a] < dep[b]) swap(a, b);
  for (int det = dep[a] - dep[b], i = 0; det; det >>= 1, ++i)
    if (det & 1) a = fa[a][i];
  if (a == b) return a;
  for (int i = 18; i >= 0; --i)
    if (fa[a][i] != fa[b][i]) {
      a = fa[a][i];
      b = fa[b][i];
    }
  return fa[a][0];
}
inline Node mergeS(const Node& a, const Node& b) {
  if (a.quan == -1) return b;
  Node ret;
  ret.quan = lca(a.quan, b.quan);
  for (auto& s : a.shao) {
    int tmp = lca(s.second, b.quan);
    if (tmp != ret.quan) ret.shao.push_back(pair<int, int>(s.first, tmp));
  }
  for (auto& s : b.shao) {
    int tmp = lca(s.second, a.quan);
    if (tmp != ret.quan) ret.shao.push_back(pair<int, int>(s.first, tmp));
  }
  return ret;
}
int main() {
  scanf("%d %d", &N, &Q);
  init();
  fa[1][0] = 1;
  for (int i = 2; i <= N; ++i) {
    scanf("%d", fa[i]);
    addEdge(fa[i][0], i);
  }
  dfs(1, 0);
  for (int i = 1; i <= N; ++i) {
    shao[i][0] = Node{i};
    shao[i][0].shao.push_back(pair<int, int>(i, -1));
  }
  for (int p = 1; (1 << p) <= N; ++p)
    for (int i = 1; i + (1 << p) - 1 <= N; ++i) {
      shao[i][p] = mergeS(shao[i][p - 1], shao[i + (1 << (p - 1))][p - 1]);
      MMMM = max(MMMM, shao[i][p].shao.size());
    }
  if (MMMM > 5)
    while (1)
      ;
  while (Q--) {
    int L, R;
    scanf("%d %d", &L, &R);
    int len = R - L + 1;
    Node ans{-1};
    for (int i = 0; (1 << i) <= len; ++i)
      if (len & (1 << i)) {
        ans = mergeS(ans, shao[L][i]);
        L += (1 << i);
      }
    int shao = R, ansDep = dep[ans.quan];
    for (auto& s : ans.shao)
      if (dep[s.second] > ansDep) {
        ansDep = dep[s.second];
        shao = s.first;
      }
    printf("%d %d\n", shao, ansDep);
  }
  return 0;
}
