#include <bits/stdc++.h>
using namespace std;
const long long N = 5e5 + 5;
const long long INF = 1e9 + 7;
const long long LOG = 19;
long long n, Q, C = 0, in[N], out[N], B[N], D[N], spT[N][LOG + 1],
                minn[N << 2 | 1], maxx[N << 2 | 1], LCA[N << 2 | 1];
vector<long long> a[N];
void DFS(const long long &u, const long long &pre) {
  in[u] = ++C;
  B[C] = u;
  for (auto v : a[u])
    if (v != pre) {
      D[v] = D[u] + 1;
      spT[v][0] = u;
      DFS(v, u);
    }
  out[u] = ++C;
  B[C] = u;
}
inline long long lca(long long x, long long y) {
  if (x == 0) return y;
  if (y == 0) return x;
  for (long long k = LOG; k >= 0; k--)
    if (D[spT[x][k]] >= D[y]) x = spT[x][k];
  for (long long k = LOG; k >= 0; k--)
    if (D[spT[y][k]] >= D[x]) y = spT[y][k];
  for (long long k = LOG; k >= 0; k--)
    if (spT[x][k] != spT[y][k]) x = spT[x][k], y = spT[y][k];
  while (x != y) x = spT[x][0], y = spT[y][0];
  return x;
}
inline void init(const long long &k, const long long &l, const long long &r) {
  if (l == r) {
    minn[k] = in[l];
    maxx[k] = in[l];
    LCA[k] = l;
  } else {
    long long mid = (l + r) >> 1;
    init(k << 1, l, mid);
    init(k << 1 | 1, mid + 1, r);
    minn[k] = min(minn[k << 1], minn[k << 1 | 1]);
    maxx[k] = max(maxx[k << 1], maxx[k << 1 | 1]);
    LCA[k] = lca(LCA[k << 1], LCA[k << 1 | 1]);
  }
}
inline long long min1(const long long &k, const long long &l,
                      const long long &r, const long long &L,
                      const long long &R) {
  if (l > R || r < L) return INF;
  if (L <= l && r <= R)
    return minn[k];
  else {
    long long mid = (l + r) >> 1;
    return min(min1(k << 1, l, mid, L, R), min1(k << 1 | 1, mid + 1, r, L, R));
  }
}
inline long long max1(const long long &k, const long long &l,
                      const long long &r, const long long &L,
                      const long long &R) {
  if (l > R || r < L) return -INF;
  if (L <= l && r <= R)
    return maxx[k];
  else {
    long long mid = (l + r) >> 1;
    return max(max1(k << 1, l, mid, L, R), max1(k << 1 | 1, mid + 1, r, L, R));
  }
}
inline long long lca1(const long long &k, const long long &l,
                      const long long &r, const long long &L,
                      const long long &R) {
  if (l > R || r < L) return 0;
  if (L <= l && r <= R)
    return LCA[k];
  else {
    long long mid = (l + r) >> 1;
    return lca(lca1(k << 1, l, mid, L, R), lca1(k << 1 | 1, mid + 1, r, L, R));
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> Q;
  for (long long i = 2; i <= n; i++) {
    long long x;
    cin >> x;
    a[x].push_back(i);
    a[i].push_back(x);
  }
  D[1] = 1;
  DFS(1, 1);
  for (long long k = 1; k <= LOG; k++)
    for (long long i = 1; i <= n; i++) spT[i][k] = spT[spT[i][k - 1]][k - 1];
  init(1, 1, n);
  while (Q--) {
    long long l, r;
    cin >> l >> r;
    long long s1 = B[min1(1, 1, n, l, r)];
    long long v1 = lca(lca1(1, 1, n, l, s1 - 1), lca1(1, 1, n, s1 + 1, r));
    long long s2 = B[max1(1, 1, n, l, r)];
    long long v2 = lca(lca1(1, 1, n, l, s2 - 1), lca1(1, 1, n, s2 + 1, r));
    if (D[v1] < D[v2])
      cout << s2 << " " << D[v2] - 1 << endl;
    else
      cout << s1 << " " << D[v1] - 1 << endl;
  }
  return 0;
}
