#include <bits/stdc++.h>
using namespace std;
template <class T>
struct SparseTable {
  std::vector<std::vector<T>> f;
  std::vector<int> lg;
  SparseTable() {}
  SparseTable(const std::vector<T>& a) { init(a); }
  void init(const std::vector<T>& a) {
    int n = a.size();
    lg.assign(n + 1, 0);
    for (int i = 1, j = 0; i <= n; i++) {
      if (i == (1 << (j + 1))) j++;
      lg[i] = j;
    }
    f.assign(lg.back() + 1, std::vector<T>(a.size()));
    f[0] = a;
    for (int j = 1; (1 << j) <= n; j++) {
      for (int i = 0; i + (1 << j) - 1 < n; i++) {
        f[j][i] = min(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);
      }
    }
  }
  T query(int l, int r) {
    int j = lg[r - l + 1];
    return min(f[j][l], f[j][r - (1 << j) + 1]);
  }
};
struct LCA {
  const std::vector<std::vector<int>>& g;
  SparseTable<std::pair<int, int>> st;
  std::vector<int> sp;
  std::vector<int> dep, ST, ED;
  LCA(const std::vector<std::vector<int>>& graph, int root = 1) : g(graph) {
    int sz = graph.size();
    dep = ST = ED = std::vector<int>(sz);
    dfs(root, -1, 0);
    std::vector<std::pair<int, int>> vec;
    for (int i = 0; i < sp.size(); i++) {
      vec.emplace_back(ST[sp[i]], sp[i]);
    }
    st.init(vec);
  }
  void dfs(int u, int fa, int d) {
    dep[u] = d + 1;
    ST[u] = sp.size();
    sp.push_back(u);
    for (auto v : g[u]) {
      if (v != fa) {
        dfs(v, u, d + 1);
        sp.push_back(u);
      }
    }
    ED[u] = (int)sp.size() - 1;
  }
  int query(int u, int v) {
    int l = ST[u], r = ST[v];
    if (l > r) std::swap(l, r);
    return st.query(l, r).second;
  }
};
int main() {
  std::ios_base::sync_with_stdio(false);
  int n, Q;
  cin >> n >> Q;
  vector<vector<int>> g(n + 1);
  for (int i = 2; i <= n; i++) {
    int p;
    cin >> p;
    g[p].push_back(i);
  }
  LCA lc(g, 1);
  std::vector<std::vector<pair<int, int>>> f1, f2;
  std::vector<std::vector<int>> f3;
  std::vector<int> lg;
  lg.assign(n + 1, 0);
  for (int i = 1, j = 0; i <= n; i++) {
    if (i == (1 << (j + 1))) j++;
    lg[i] = j;
  }
  f1.assign(lg.back() + 1, std::vector<pair<int, int>>(n));
  f2.assign(lg.back() + 1, std::vector<pair<int, int>>(n));
  f3.assign(lg.back() + 1, std::vector<int>(n + 1));
  for (int i = 0; i < n; i++) {
    f1[0][i] = f2[0][i] = {lc.ST[i + 1], i + 1};
    f3[0][i] = i + 1;
  }
  for (int j = 1; (1 << j) <= n; j++) {
    for (int i = 0; i + (1 << j) - 1 < n; i++) {
      f3[j][i] = lc.query(f3[j - 1][i], f3[j - 1][i + (1 << (j - 1))]);
      f1[j][i] = min(f1[j - 1][i], f1[j - 1][i + (1 << (j - 1))]);
      f2[j][i] = max(f2[j - 1][i], f2[j - 1][i + (1 << (j - 1))]);
    }
  }
  while (Q--) {
    int l, r;
    cin >> l >> r;
    l--, r--;
    int j = lg[r - l + 1];
    int p1 = min(f1[j][l], f1[j][r - (1 << j) + 1]).second;
    int p2 = max(f2[j][l], f2[j][r - (1 << j) + 1]).second;
    auto range_lca = [&lc, &lg, &f3](int x, int y) {
      int d = lg[y - x + 1];
      return lc.query(f3[d][x], f3[d][y - (1 << d) + 1]);
    };
    int x = -1, y = -1;
    auto update = [&](int p) {
      int c;
      p--;
      if (p == l)
        c = range_lca(l + 1, r);
      else if (p == r)
        c = range_lca(l, r - 1);
      else
        c = lc.query(range_lca(l, p - 1), range_lca(p + 1, r));
      if (x == -1 || lc.dep[c] > lc.dep[x]) {
        x = c, y = p + 1;
      }
    };
    update(p1);
    update(p2);
    cout << y << " " << lc.dep[x] - 1 << endl;
  }
  return 0;
}
