#include <bits/stdc++.h>
using namespace std;
const int N = (int)2e5 + 123;
const int mod = 1e9 + 7;
const long long inf = 1e18 + 9;
inline void boost() {
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
}
int n, q, pr[25][N];
int tin[N], tout[N], timer;
vector<int> g[N];
int dp[25][N], lg[N], lvl[N];
int mn[4 * N], mx[4 * N];
void dfs(int v = 1, int p = 0) {
  tin[v] = ++timer;
  if (p > 0) lvl[v] = lvl[p] + 1;
  for (int i = 1; i <= 20; i++) pr[i][v] = pr[i - 1][pr[i - 1][v]];
  for (auto to : g[v]) {
    if (to == p) continue;
    dfs(to, v);
  }
  tout[v] = timer;
}
bool is(int a, int b) { return (tin[a] <= tin[b] && tout[a] >= tout[b]); }
int LCA(int a, int b) {
  if (is(a, b)) return a;
  if (is(b, a)) return b;
  for (int i = 20; i >= 0; i--)
    if (pr[i][a] && !is(pr[i][a], b)) a = pr[i][a];
  return pr[0][a];
}
int get(int l, int r) {
  int Lg = lg[r - l + 1];
  return LCA(dp[Lg][l], dp[Lg][r - (1 << Lg) + 1]);
}
int g1(int l, int r, int v = 1, int tl = 1, int tr = n) {
  if (tl > r || tr < l || l > r || tl > tr) return n + 1;
  if (l <= tl && tr <= r) return mn[v];
  int tm = (tl + tr) >> 1;
  int x = g1(l, r, v + v, tl, tm);
  int y = g1(l, r, v + v + 1, tm + 1, tr);
  if (tin[x] < tin[y]) return x;
  return y;
}
int g2(int l, int r, int v = 1, int tl = 1, int tr = n) {
  if (tl > r || tr < l || l > r || tl > tr) return 0;
  if (l <= tl && tr <= r) {
    return mx[v];
  }
  int tm = (tl + tr) >> 1;
  int x = g2(l, r, v + v, tl, tm);
  int y = g2(l, r, v + v + 1, tm + 1, tr);
  if (tin[x] > tin[y]) return x;
  return y;
}
void build(int v = 1, int tl = 1, int tr = n) {
  if (tl == tr) {
    mn[v] = mx[v] = tl;
    return;
  }
  int tm = (tl + tr) >> 1;
  build(v + v, tl, tm);
  build(v + v + 1, tm + 1, tr);
  if (tin[mn[v + v]] < tin[mn[v + v + 1]]) {
    mn[v] = mn[v + v];
  } else {
    mn[v] = mn[v + v + 1];
  }
  if (tin[mx[v + v]] > tin[mx[v + v + 1]]) {
    mx[v] = mx[v + v];
  } else {
    mx[v] = mx[v + v + 1];
  }
}
int main() {
  boost();
  cin >> n >> q;
  for (int i = 2; i <= n; i++) {
    int p;
    cin >> p;
    pr[0][i] = p;
    g[p].push_back(i);
    g[i].push_back(p);
  }
  dfs();
  for (int i = 1; i <= n; i++) {
    dp[0][i] = i;
    lg[i] = -1;
  }
  lg[1] = 0;
  for (int i = 1; i <= n; i++) {
    if (lg[i] == -1)
      lg[i] = lg[i - 1];
    else
      lg[i * 2] = lg[i] + 1;
  }
  tin[n + 1] = mod;
  tin[0] = -mod;
  for (int i = 1; i <= 20; i++)
    for (int j = 1; j + (1 << (i - 1)) <= n; j++) {
      dp[i][j] = LCA(dp[i - 1][j], dp[i - 1][j + (1 << i - 1)]);
    }
  build();
  while (q--) {
    int l, r;
    cin >> l >> r;
    int mn = g1(l, r);
    int mx = g2(l, r);
    int ans = 0;
    int lca;
    if (mn == l)
      lca = get(l + 1, r);
    else if (mn == r)
      lca = get(l, r - 1);
    else
      lca = LCA(get(l, mn - 1), get(mn + 1, r));
    ans = max(ans, lvl[lca]);
    if (mx == l)
      lca = get(l + 1, r);
    else if (mx == r)
      lca = get(l, r - 1);
    else
      lca = LCA(get(l, mx - 1), get(mx + 1, r));
    if (lvl[lca] > ans)
      cout << mx << ' ' << lvl[lca] << endl;
    else
      cout << mn << ' ' << ans << endl;
  }
  return 0;
}
