#include <bits/stdc++.h>
#pragma GCC optimize("-O2")
using namespace std;
void err(istream_iterator<string> it) {}
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " = " << a << endl;
  err(++it, args...);
}
const int LIM = 1e5 + 5, MOD = 1e9 + 7;
int t, n, m, k, x, y;
int l;
vector<vector<int>> adj;
int timer;
vector<int> tin, tout, height;
vector<vector<int>> up;
void dfs(int v, int p) {
  tin[v] = ++timer;
  up[v][0] = p;
  height[v] = height[p] + 1;
  for (int i = 1; i <= l; ++i) up[v][i] = up[up[v][i - 1]][i - 1];
  for (int u : adj[v]) {
    if (u != p) dfs(u, v);
  }
  tout[v] = ++timer;
}
bool is_ancetor(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }
int lca(int u, int v) {
  if (is_ancetor(u, v)) return u;
  if (is_ancetor(v, u)) return v;
  for (int i = l; i >= 0; --i) {
    if (!is_ancetor(up[u][i], v)) u = up[u][i];
  }
  return up[u][0];
}
pair<int, int> Tm[4 * LIM], TM[4 * LIM];
pair<int, int> combine2(pair<int, int> a, pair<int, int> b) {
  if (a.first >= b.first) return a;
  return b;
}
pair<int, int> combine1(pair<int, int> a, pair<int, int> b) {
  if (a.first < b.first) return a;
  return b;
}
void build(vector<int>& a, int v, int tl, int tr) {
  if (tl == tr) {
    Tm[v] = make_pair(a[tl], tl);
    TM[v] = make_pair(a[tl], tl);
  } else {
    int tm = (tl + tr) / 2;
    build(a, v * 2, tl, tm);
    build(a, v * 2 + 1, tm + 1, tr);
    Tm[v] = combine1(Tm[v * 2], Tm[v * 2 + 1]);
    TM[v] = combine2(TM[v * 2], TM[v * 2 + 1]);
  }
}
pair<int, int> get_max(int v, int tl, int tr, int l, int r) {
  if (l > r) return make_pair(-MOD, -1);
  if (l == tl && r == tr) return TM[v];
  int tm = (tl + tr) / 2;
  return combine2(get_max(v * 2, tl, tm, l, min(r, tm)),
                  get_max(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
}
pair<int, int> get_min(int v, int tl, int tr, int l, int r) {
  if (l > r) return make_pair(MOD, -1);
  if (l == tl && r == tr) return Tm[v];
  int tm = (tl + tr) / 2;
  return combine1(get_min(v * 2, tl, tm, l, min(r, tm)),
                  get_min(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
}
void preprocess(int root) {
  tin.resize(n);
  tout.resize(n);
  timer = 0;
  height.resize(n);
  l = ceil(log2(n));
  up.assign(n, vector<int>(l + 1));
  height[root] = -1;
  dfs(root, root);
  build(tin, 1, 0, n - 1);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  adj.assign(n, vector<int>(0));
  for (int i = 1; i < n; i++) {
    cin >> x;
    --x;
    adj[x].push_back(i);
    adj[i].push_back(x);
  }
  preprocess(0);
  for (int i = 0; i < m; i++) {
    cin >> x >> y;
    --x;
    --y;
    int mni = get_min(1, 0, n - 1, x, y).second;
    int mxi = get_max(1, 0, n - 1, x, y).second;
    int l1, r1, l2, r2;
    pair<int, int> mn1, mn2, mx1, mx2;
    l1 = x;
    r1 = mni - 1;
    if (r1 < l1) {
      mn1 = make_pair(MOD, -1), mx1 = make_pair(-MOD, -1);
    } else {
      mn1 = get_min(1, 0, n - 1, l1, r1);
      mx1 = get_max(1, 0, n - 1, l1, r1);
    }
    l2 = mni + 1;
    r2 = y;
    if (l2 > r2) {
      mn2 = make_pair(MOD, -1);
      mx2 = make_pair(-MOD, -1);
    } else {
      mn2 = get_min(1, 0, n - 1, l2, r2);
      mx2 = get_max(1, 0, n - 1, l2, r2);
    }
    mn1 = min(mn1, mn2);
    mx1 = max(mx1, mx2);
    int ans1 = height[lca(mn1.second, mx1.second)];
    l1 = x;
    r1 = mxi - 1;
    if (r1 < l1) {
      mn1 = make_pair(MOD, -1), mx1 = make_pair(-MOD, -1);
    } else {
      mn1 = get_min(1, 0, n - 1, l1, r1);
      mx1 = get_max(1, 0, n - 1, l1, r1);
    }
    l2 = mxi + 1;
    r2 = y;
    if (l2 > r2) {
      mn2 = make_pair(MOD, -1), mx2 = make_pair(-MOD, -1);
    } else {
      mn2 = get_min(1, 0, n - 1, l2, r2);
      mx2 = get_max(1, 0, n - 1, l2, r2);
    }
    mn1 = min(mn1, mn2);
    mx1 = max(mx1, mx2);
    int ans2 = height[lca(mn1.second, mx1.second)];
    if (ans1 >= ans2) {
      cout << 1 + mni << " " << ans1 << "\n";
    } else {
      cout << 1 + mxi << " " << ans2 << "\n";
    }
  }
  return 0;
}
