#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
const int inf = 0x3f3f3f3f;
int ans[maxn], in[maxn], out[maxn], node_id[maxn + maxn], dfs_idx, dep[maxn],
    del_pt[maxn];
vector<int> g[maxn];
int bit[maxn + maxn];
struct Status {
  int l, id, del;
  Status(int _l = 0, int _id = 0, int _del = 0) : l(_l), id(_id), del(_del) {}
};
vector<Status> qry[maxn + maxn];
inline int lowbit(int x) { return x & -x; }
inline void modify(int pos, int v) {
  for (int i = pos; i <= dfs_idx; i += lowbit(i)) bit[i] = max(bit[i], v);
}
inline int query(int pos) {
  int res = 0;
  for (int i = pos; i > 0; i -= lowbit(i)) res = max(res, bit[i]);
  return res;
}
void dfs(int u) {
  in[u] = ++dfs_idx;
  node_id[in[u]] = u;
  for (int i = 0; i < (int)g[u].size(); i++) {
    int v = g[u][i];
    dep[v] = dep[u] + 1;
    dfs(v);
  }
  out[u] = ++dfs_idx;
  node_id[out[u]] = u;
}
struct Segment {
  int minv, sec_minv;
  int maxv, sec_maxv;
} seg[maxn << 2];
Segment merge(Segment lhs, Segment rhs) {
  Segment mg;
  mg.minv = lhs.minv;
  mg.sec_minv = rhs.minv;
  mg.maxv = lhs.maxv;
  mg.sec_maxv = rhs.maxv;
  if (mg.minv > mg.sec_minv) swap(mg.minv, mg.sec_minv);
  if (mg.maxv < mg.sec_maxv) swap(mg.maxv, mg.sec_maxv);
  if (mg.sec_minv > lhs.sec_minv) mg.sec_minv = lhs.sec_minv;
  if (mg.sec_minv > rhs.sec_minv) mg.sec_minv = rhs.sec_minv;
  if (mg.sec_maxv < lhs.sec_maxv) mg.sec_maxv = lhs.sec_maxv;
  if (mg.sec_maxv < rhs.sec_maxv) mg.sec_maxv = rhs.sec_maxv;
  return mg;
}
void build(int l, int r, int idx) {
  if (l == r) {
    seg[idx].minv = in[l];
    seg[idx].maxv = out[l];
    seg[idx].sec_minv = inf;
    seg[idx].sec_maxv = -inf;
  } else {
    int mid = (l + r) >> 1;
    build(l, mid, idx << 1);
    build(mid + 1, r, idx << 1 | 1);
    seg[idx] = merge(seg[idx << 1], seg[idx << 1 | 1]);
  }
}
Segment query(int l, int r, int ql, int qr, int idx) {
  if (l == ql && r == qr) return seg[idx];
  int mid = (l + r) >> 1;
  if (qr <= mid)
    return query(l, mid, ql, qr, idx << 1);
  else if (ql > mid)
    return query(mid + 1, r, ql, qr, idx << 1 | 1);
  return merge(query(l, mid, ql, mid, idx << 1),
               query(mid + 1, r, mid + 1, qr, idx << 1 | 1));
}
int main() {
  int n, q, p, l, r;
  scanf("%d%d", &n, &q);
  for (int i = 2; i <= n; i++) {
    scanf("%d", &p);
    g[p].push_back(i);
  }
  dfs(1);
  build(1, n, 1);
  for (int i = 1; i <= q; i++) {
    scanf("%d %d", &l, &r);
    Segment q = query(1, n, l, r, 1);
    if (node_id[q.maxv] == node_id[q.minv]) {
      qry[q.sec_maxv].push_back(Status(q.sec_minv, i, node_id[q.maxv]));
    } else {
      qry[q.sec_maxv].push_back(Status(q.minv, i, node_id[q.maxv]));
      qry[q.maxv].push_back(Status(q.sec_minv, i, node_id[q.minv]));
    }
  }
  for (int i = dfs_idx; i >= 1; i--) {
    int node = node_id[i];
    if (i == out[node]) modify(in[node], dep[node]);
    for (int j = 0; j < (int)qry[i].size(); j++) {
      int q = query(qry[i][j].l);
      if (q >= ans[qry[i][j].id]) {
        ans[qry[i][j].id] = q;
        del_pt[qry[i][j].id] = qry[i][j].del;
      }
    }
  }
  for (int i = 1; i <= q; i++) printf("%d %d\n", del_pt[i], ans[i]);
  return 0;
}
