#include <bits/stdc++.h>
using namespace std;
class lca {
 public:
  int n, logn;
  vector<vector<int>> parent;
  vector<int> depth;
  lca(vector<vector<int>> &tree, int rt = 0) {
    n = (int)tree.size(), logn = log2(n) + 1;
    parent.resize(n, vector<int>(logn));
    depth.resize(n);
    function<void(int, int, int)> dfs = [&](int u, int p, int d) {
      parent[u][0] = p;
      depth[u] = d;
      for (int v : tree[u]) {
        if (v == p) continue;
        dfs(v, u, d + 1);
      }
    };
    dfs(rt, -1, 0);
    for (int k = 0; k + 1 < logn; k++) {
      for (int u = 0; u < n; u++) {
        if (parent[u][k] < 0) {
          parent[u][k + 1] = -1;
        } else {
          parent[u][k + 1] = parent[parent[u][k]][k];
        }
      }
    }
  }
  int get(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    for (int k = 0; k < logn; k++) {
      if ((depth[v] - depth[u]) >> k & 1) {
        v = parent[v][k];
      }
    }
    if (u == v) return u;
    for (int k = logn - 1; k >= 0; k--) {
      if (parent[u][k] != parent[v][k]) {
        u = parent[u][k];
        v = parent[v][k];
      }
    }
    return parent[u][0];
  }
  int log2(int b) { return 31 - __builtin_clz(b); }
};
template <typename T>
class sparse_table {
 public:
  int n, m;
  vector<vector<int>> dp;
  vector<vector<int>> pd;
  sparse_table() {}
  sparse_table(vector<T> &a) { init(a); }
  void init(vector<T> &a) {
    n = a.size(), m = log2(n) + 1;
    dp.resize(n, vector<int>(m));
    pd.resize(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
      dp[i][0] = i;
      pd[i][0] = i;
    }
    for (int j = 1, k = 1; j < m; j++, k <<= 1) {
      for (int i = 0; i + k < n; i++) {
        dp[i][j] = a[dp[i][j - 1]] <= a[dp[i + k][j - 1]] ? dp[i][j - 1]
                                                          : dp[i + k][j - 1];
        pd[i][j] = a[pd[i][j - 1]] <= a[pd[i + k][j - 1]] ? pd[i + k][j - 1]
                                                          : pd[i][j - 1];
      }
    }
  }
  int query_min(int l, int r, vector<T> &a) {
    int k = log2(r - l);
    return a[dp[l][k]] <= a[dp[r - (1 << k)][k]] ? dp[l][k]
                                                 : dp[r - (1 << k)][k];
  }
  int query_max(int l, int r, vector<T> &a) {
    int k = log2(r - l);
    return a[pd[l][k]] <= a[pd[r - (1 << k)][k]] ? pd[r - (1 << k)][k]
                                                 : pd[l][k];
  }
  int log2(int b) { return 31 - __builtin_clz(b); }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(15);
  int n, q;
  cin >> n >> q;
  vector<vector<int>> tree(n);
  for (int i = 1; i < n; i++) {
    int p;
    cin >> p;
    p--;
    tree[p].push_back(i);
  }
  vector<int> in(n), depth(n);
  int k = 0;
  function<void(int, int, int)> dfs = [&](int u, int p, int d) {
    in[u] = k++;
    depth[u] = d;
    for (int v : tree[u]) {
      if (v == p) continue;
      dfs(v, u, d + 1);
    }
  };
  dfs(0, -1, 0);
  lca lc(tree);
  sparse_table<int> rmqin(in);
  auto get_range = [&](int l, int r) {
    int u = rmqin.query_max(l, r + 1, in);
    int v = rmqin.query_min(l, r + 1, in);
    return lc.get(u, v);
  };
  auto get_ans = [&](int l, int r, int u) {
    int a = -1, b = -1;
    if (l <= u - 1) {
      a = get_range(l, u - 1);
    }
    if (u + 1 <= r) {
      b = get_range(u + 1, r);
    }
    int anc = max(a, b);
    if (a != -1 && b != -1) {
      anc = lc.get(a, b);
    }
    return make_pair(depth[anc], u);
  };
  while (q--) {
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    int u = rmqin.query_max(l, r + 1, in);
    int v = rmqin.query_min(l, r + 1, in);
    pair<int, int> ans = max(get_ans(l, r, u), get_ans(l, r, v));
    cout << ans.second + 1 << ' ' << ans.first << '\n';
  }
  return 0;
}
