#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
long long gcd(long long a, long long b) { return (a == 0) ? b : gcd(b % a, a); }
long long cnt1(long long x) {
  long long cnt = 0;
  while (x > 0) x &= x - 1, cnt++;
  return cnt;
}
long long fact(long long n) { return n == 0 ? 1LL : n * fact(n - 1); }
long long fact(long long n, long long p) {
  return n == 0 ? 1LL : n * fact(n - 1) % p;
}
long long cnk(long long n, long long k) {
  return n == 1 || k == 1 ? 1 : cnk(n - 1, k) + cnk(n - 1, k - 1);
}
long long pow(long long a, long long n, long long p) {
  if (n == 0) return 1;
  long long t = pow(a, n / 2, p);
  return t * t * (n % 2 ? a : 1);
}
long long cnk(long long n, long long k, long long p) {
  return fact(n, p) * pow(fact(k, p), p - 2, p) * pow(fact(n - k, p), p - 2, p);
}
template <class T>
istream &operator>>(istream &is, vector<T> &v) {
  for (long long i = 0; i < v.size(); i++) is >> v[i];
  return is;
}
template <class T>
ostream &operator<<(ostream &os, vector<T> v) {
  for (long long i = 0; i < v.size(); i++) os << v[i] << ' ';
  os << '\n';
  return os;
}
const long long N = 1e+5 + 10, LOG = 20;
vector<long long> a;
long long tin[N], h[N];
vector<long long> gr[N];
void dfs(long long v, long long curh = 0) {
  h[v] = curh;
  tin[v] = a.size();
  a.push_back(v);
  for (long long u : gr[v]) dfs(u, curh + 1);
}
long long p[N][LOG];
long long lca(long long a, long long b) {
  if (h[a] > h[b]) swap(a, b);
  for (long long log = LOG - 1; log >= 0; log--)
    if (h[b] - (1 << log) >= h[a]) b = p[b][log];
  if (a == b) return a;
  for (long long log = LOG - 1; log >= 0; log--)
    if (p[a][log] != p[b][log]) {
      a = p[a][log];
      b = p[b][log];
    }
  return p[a][0];
}
long long imax[1 << 18], imin[1 << 18];
void build(long long v, long long l, long long r) {
  if (r - l == 1)
    imax[v] = imin[v] = l;
  else {
    long long m = (r + l) >> 1;
    build(2 * v + 1, l, m);
    build(2 * v + 2, m, r);
    if (tin[imin[2 * v + 1]] < tin[imin[2 * v + 2]])
      imin[v] = imin[2 * v + 1];
    else
      imin[v] = imin[2 * v + 2];
    if (tin[imax[2 * v + 1]] > tin[imax[2 * v + 2]])
      imax[v] = imax[2 * v + 1];
    else
      imax[v] = imax[2 * v + 2];
  }
}
pair<long long, long long> get(long long v, long long l, long long r,
                               long long ql, long long qr) {
  if (qr <= l || r <= ql)
    return {-1, -1};
  else if (ql <= l && r <= qr)
    return {imin[v], imax[v]};
  else {
    long long m = (r + l) >> 1;
    auto x = get(2 * v + 1, l, m, ql, qr);
    auto y = get(2 * v + 2, m, r, ql, qr);
    pair<long long, long long> ans;
    if (x.first == -1)
      ans.first = y.first;
    else if (y.first == -1)
      ans.first = x.first;
    else {
      if (tin[x.first] < tin[y.first])
        ans.first = x.first;
      else
        ans.first = y.first;
    }
    if (x.second == -1)
      ans.second = y.second;
    else if (y.second == -1)
      ans.second = x.second;
    else {
      if (tin[x.second] > tin[y.second])
        ans.second = x.second;
      else
        ans.second = y.second;
    }
    return ans;
  }
}
long long n;
long long get_ans(long long l, long long r, long long er) {
  if (l == er) {
    auto tmp = get(0, 0, n, er + 1, r);
    return lca(tmp.first, tmp.second);
  } else if (r - 1 == er) {
    auto tmp = get(0, 0, n, l, er);
    return lca(tmp.first, tmp.second);
  }
  auto tmp1 = get(0, 0, n, l, er);
  long long lca1 = lca(tmp1.first, tmp1.second);
  auto tmp2 = get(0, 0, n, er + 1, r);
  long long lca2 = lca(tmp2.first, tmp2.second);
  return lca(lca1, lca2);
}
signed main() {
  srand(time(0));
  ios_base::sync_with_stdio(0), cin.tie(0);
  memset(p, -1, sizeof p);
  long long q;
  cin >> n >> q;
  for (long long i = 1; i < n; i++) {
    cin >> p[i][0];
    p[i][0]--;
    gr[p[i][0]].push_back(i);
  }
  dfs(0);
  build(0, 0, n);
  for (long long l = 1; l < LOG; l++)
    for (long long i = 0; i < n; i++) {
      if (p[i][l - 1] == -1) continue;
      p[i][l] = p[p[i][l - 1]][l - 1];
    }
  while (q--) {
    long long l, r;
    cin >> l >> r;
    l--;
    auto tmp = get(0, 0, n, l, r);
    long long lca1 = get_ans(l, r, tmp.first), lca2 = get_ans(l, r, tmp.second);
    if (h[lca1] > h[lca2])
      cout << tmp.first + 1 << ' ' << h[lca1];
    else
      cout << tmp.second + 1 << ' ' << h[lca2];
    cout << '\n';
  }
}
