#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000;
int n, q, H[maxn + 1], cnt, Tin[maxn + 1], P[maxn + 1][17], R[maxn + 1][17],
    R1[maxn + 1][17], R2[maxn + 1][17];
vector<int> G[maxn + 1];
void input() {
  cin >> n >> q;
  for (int _b = n, i = 2; i <= _b; ++i) {
    int p;
    cin >> p;
    G[p].push_back(i);
    G[i].push_back(p);
  }
}
void dfs(int u, int dad, int depth) {
  H[u] = depth;
  Tin[u] = ++cnt;
  P[u][0] = dad;
  for (int _b = 16, j = 1; j <= _b; ++j) P[u][j] = P[P[u][j - 1]][j - 1];
  for (auto &v : G[u]) {
    if (v == dad) continue;
    dfs(v, u, depth + 1);
  }
}
int lca(int u, int v) {
  if (u == 0) return v;
  if (v == 0) return u;
  if (H[u] > H[v]) swap(u, v);
  int diff = H[v] - H[u];
  for (int _b = 0, j = 16; j >= _b; --j)
    if (diff >> j & 1) v = P[v][j];
  if (u == v) return u;
  for (int _b = 0, j = 16; j >= _b; --j)
    if (P[u][j] != P[v][j]) u = P[u][j], v = P[v][j];
  return P[u][0];
}
int cmp1(int u, int v) { return (Tin[u] < Tin[v] ? u : v); }
int cmp2(int u, int v) { return (Tin[u] > Tin[v] ? u : v); }
void buildR() {
  for (int _b = n, i = 1; i <= _b; ++i) R[i][0] = R1[i][0] = R2[i][0] = i;
  for (int _b = 16, j = 1; j <= _b; ++j)
    for (int _b = n - (1 << j) + 1, i = 1; i <= _b; ++i) {
      R[i][j] = lca(R[i][j - 1], R[i + (1 << (j - 1))][j - 1]);
      R1[i][j] = cmp1(R1[i][j - 1], R1[i + (1 << (j - 1))][j - 1]);
      R2[i][j] = cmp2(R2[i][j - 1], R2[i + (1 << (j - 1))][j - 1]);
    }
}
int lcaseg(int l, int r) {
  if (l > r) return 0;
  int x = log2(r - l + 1);
  return lca(R[l][x], R[r - (1 << x) + 1][x]);
}
int getmin(int l, int r) {
  int x = log2(r - l + 1);
  return cmp1(R1[l][x], R1[r - (1 << x) + 1][x]);
}
int getmax(int l, int r) {
  int x = log2(r - l + 1);
  return cmp2(R2[l][x], R2[r - (1 << x) + 1][x]);
}
int res1, res2;
void getres(int pos, int u, int v) {
  int x = lca(lcaseg(u, pos - 1), lcaseg(pos + 1, v));
  if (H[x] > H[res2]) {
    res1 = pos;
    res2 = x;
  }
}
void solve() {
  dfs(1, 1, 0);
  buildR();
  while (q--) {
    int u, v;
    cin >> u >> v;
    res1 = u;
    res2 = 1;
    getres(getmin(u, v), u, v);
    getres(getmax(u, v), u, v);
    cout << res1 << ' ' << H[res2] << '\n';
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  input();
  solve();
  return 0;
}
