#include <bits/stdc++.h>
using namespace std;
inline int readint() {
  int a = 0;
  char c = getchar(), f = 1;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') f = -f;
  for (; '0' <= c && c <= '9'; c = getchar())
    a = (a << 3) + (a << 1) + (c ^ 48);
  return a * f;
}
const int MaxN = 100005;
int n, m;
struct Edge {
  int to, nxt;
  Edge() {}
  Edge(int T, int N) { to = T, nxt = N; }
};
Edge e[MaxN << 1];
int cntEdge, head[MaxN];
void clear_graph() {
  for (int i = 1; i <= n; ++i) head[i] = -1;
  cntEdge = 0;
}
void addEdge(int a, int b) {
  e[cntEdge] = Edge(b, head[a]);
  head[a] = cntEdge++;
}
int dep[MaxN];
int fa[MaxN][20];
int dfn[MaxN], dfsClock;
void build(int x, int pre = 0) {
  dfn[x] = ++dfsClock;
  dep[x] = dep[pre] + 1;
  fa[x][0] = pre;
  for (int j = 0; j + 1 < 20; ++j) {
    if (fa[x][j] == 0) break;
    fa[x][j + 1] = fa[fa[x][j]][j];
  }
  for (int i = head[x]; ~i; i = e[i].nxt)
    if (e[i].to != pre) build(e[i].to, x);
}
int getLca(int a, int b) {
  if (!a || !b) return a + b;
  if (dep[a] < dep[b]) swap(a, b);
  for (int j = 19; ~j; --j)
    if ((dep[a] - dep[b]) >> j & 1) a = fa[a][j];
  if (a == b) return a;
  for (int j = 19; ~j; --j)
    if (fa[a][j] != fa[b][j]) a = fa[a][j], b = fa[b][j];
  return fa[a][0];
}
namespace UFS {
int fa[MaxN], rnk[MaxN];
int val[MaxN];
void init() {
  for (int i = 1; i <= n; ++i) {
    fa[i] = val[i] = i;
    rnk[i] = 1;
  }
}
inline int find(int a) {
  if (a != fa[a]) fa[a] = find(fa[a]);
  return fa[a];
}
void combine(int a, int b) {
  a = find(a), b = find(b);
  if (rnk[a] > rnk[b]) swap(a, b);
  if (dep[val[a]] < dep[val[b]]) val[b] = val[a];
  fa[a] = b, rnk[b] += rnk[a];
}
}  // namespace UFS
vector<int> q[MaxN];
bool vis[MaxN];
void tarjan(int x, int pre = 0) {
  for (int i = head[x]; ~i; i = e[i].nxt)
    if (e[i].to != pre) {
      tarjan(e[i].to, x);
      UFS::combine(e[i].to, x);
    }
  vis[x] = true;
  int len = q[x].size();
  for (int i = 0, y; i < len; ++i)
    if (vis[y = q[x][i]]) {
      y = UFS::find(y);
      q[x][i] = UFS::val[y];
    } else
      q[x][i] = -1;
}
int lca[20][MaxN], lg2[MaxN];
int st1[20][MaxN];
int st2[20][MaxN];
void prepare() {
  lg2[1] = 0;
  for (int i = 2; i <= n; ++i) lg2[i] = lg2[i >> 1] + 1;
  for (int i = 1; i <= n; ++i) {
    st1[0][i] = st2[0][i] = i;
    lca[0][i] = i;
  }
  for (int j = 1; (1 << j) <= n; ++j) {
    int len = (1 << j >> 1);
    for (int i = 1; i + len * 2 - 1 <= n; ++i) {
      int a = lca[j - 1][i];
      int b = lca[j - 1][i + len];
      q[a].push_back(b);
      q[b].push_back(a);
      a = st1[j - 1][i];
      b = st1[j - 1][i + len];
      if (dfn[a] < dfn[b])
        st1[j][i] = a;
      else
        st1[j][i] = b;
      a = st2[j - 1][i];
      b = st2[j - 1][i + len];
      if (dfn[a] > dfn[b])
        st2[j][i] = a;
      else
        st2[j][i] = b;
    }
    for (int i = 1; i <= n; ++i) vis[i] = false;
    UFS::init();
    tarjan(1);
    for (int i = n - len * 2 + 1; i; --i) {
      int a = lca[j - 1][i];
      int b = lca[j - 1][i + len];
      if (q[a].back() != -1)
        lca[j][i] = q[a].back();
      else
        lca[j][i] = q[b].back();
      q[a].pop_back();
      q[b].pop_back();
    }
  }
}
int queryLca(int l, int r) {
  if (l > r) return 0;
  int k = lg2[r - l + 1];
  if ((1 << k) == r - l + 1) return lca[k][l];
  return getLca(lca[k][l], lca[k][r - (1 << k) + 1]);
}
pair<int, int> queryDfn(int l, int r) {
  pair<int, int> res;
  int k = lg2[r - l + 1], a, b;
  a = st1[k][l];
  b = st1[k][r - (1 << k) + 1];
  if (dfn[a] > dfn[b]) a = b;
  res.first = a;
  a = st2[k][l];
  b = st2[k][r - (1 << k) + 1];
  if (dfn[a] < dfn[b]) a = b;
  res.second = a;
  return res;
}
int main() {
  n = readint(), m = readint();
  clear_graph();
  for (int i = 2; i <= n; ++i) addEdge(readint(), i);
  build(1), prepare();
  for (int l, r; m; --m) {
    l = readint(), r = readint();
    auto away = queryDfn(l, r);
    int xjh = queryLca(l, away.first - 1);
    xjh = getLca(xjh, queryLca(away.first + 1, r));
    int xez = queryLca(l, away.second - 1);
    xez = getLca(xez, queryLca(away.second + 1, r));
    if (dep[xjh] < dep[xez]) xjh = xez, away.first = away.second;
    printf("%d %d\n", away.first, dep[xjh] - 1);
  }
  return 0;
}
