#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void Cin(T &x) {
  register char c;
  for (c = getchar(); c < '0' || c > '9'; c = getchar())
    ;
  for (x = 0; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
}
const int N = 1e5 + 2, logN = 32 - __builtin_clz(N);
static int p[N][logN], Min[N][logN], Max[N][logN], num[N], h[N];
int n, q, logn, nTime, l, r, maxh = 1;
vector<int> adj[N];
inline void DFS(int u) {
  if (h[u] > h[maxh]) maxh = u;
  Max[u][0] = Min[u][0] = u;
  num[u] = ++nTime;
  for (int j = 1; j <= logn; ++j) p[u][j] = p[p[u][j - 1]][j - 1];
  for (int v : adj[u]) h[v] = h[u] + 1, DFS(v);
}
void Prepare() {
  cin >> n >> q;
  for (int u = 2; u <= n; ++u) cin >> p[u][0], adj[p[u][0]].push_back(u);
  logn = 31 - __builtin_clz(n);
  DFS(1);
  for (int j = 0; j < logn; ++j)
    for (int u = 1; u <= n; ++u) {
      int v = u + (1 << j);
      if (v > n)
        Max[u][j + 1] = Max[u][j], Min[u][j + 1] = Min[u][j];
      else
        Max[u][j + 1] = num[Max[u][j]] > num[Max[v][j]] ? Max[u][j] : Max[v][j],
                   Min[u][j + 1] =
                       num[Min[v][j]] > num[Min[u][j]] ? Min[u][j] : Min[v][j];
    }
  num[0] = N;
}
inline int LCA(int u, int v) {
  if (h[u] < h[v]) swap(u, v);
  for (int del = h[u] - h[v], j = log2(del); j >= 0; --j)
    if (del >> j & 1) u = p[u][j];
  if (u == v) return u;
  for (int j = logn; j >= 0; --j)
    if (p[u][j] != p[v][j]) v = p[v][j], u = p[u][j];
  return p[u][0];
}
struct TPair {
  int u, v;
};
inline TPair Calc(int l, int r) {
  if (l > r) return {0, n + 1};
  int k = 31 - __builtin_clz(r - l + 1);
  r -= (1 << k) - 1;
  return {num[Min[l][k]] < num[Min[r][k]] ? Min[l][k] : Min[r][k],
          num[Max[r][k]] < num[Max[l][k]] ? Max[l][k] : Max[r][k]};
}
inline int Get(int m) {
  TPair a = Calc(l, m - 1), b = Calc(m + 1, r);
  return h[LCA(num[a.u] < num[b.u] ? a.u : b.u,
               num[b.v] < num[a.v] ? a.v : b.v)];
}
void Solve() {
  while (--q >= 0) {
    cin >> l >> r;
    if (l == r) {
      cout << maxh << ' ' << h[maxh] << '\n';
      continue;
    }
    TPair a = Calc(l, r);
    int val1 = Get(a.u), val2 = Get(a.v);
    if (val1 > val2)
      cout << a.u << ' ' << val1 << '\n';
    else
      cout << a.v << ' ' << val2 << '\n';
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  Prepare();
  Solve();
  return 0;
}
