#include <bits/stdc++.h>
using namespace std;
int N, Q;
vector<int> adj[100005];
bool vis[100005];
int depth[100005];
int anc[100005][21];
int pre[100005], pst[100005], tt = 0;
void dfs(int u) {
  vis[u] = 1;
  pre[u] = ++tt;
  for (int j = 1; j <= 20; j++) {
    if (depth[u] <= (1 << j)) break;
    anc[u][j] = anc[anc[u][j - 1]][j - 1];
  }
  int v;
  for (int k = 0; k < adj[u].size(); k++) {
    v = adj[u][k];
    if (vis[v]) continue;
    depth[v] = depth[u] + 1;
    anc[v][0] = u;
    dfs(v);
  }
  pst[u] = tt;
}
int lca(int u, int v) {
  if (depth[u] < depth[v]) swap(u, v);
  for (int j = 20; j >= 0; j--) {
    if (depth[anc[u][j]] >= depth[v]) {
      u = anc[u][j];
    }
  }
  if (u == v) return u;
  for (int j = 20; j >= 0; j--) {
    if (anc[u][j] != anc[v][j]) {
      u = anc[u][j];
      v = anc[v][j];
    }
  }
  return anc[u][0];
}
int dp[2][100005][21], dp_id[2][100005][21];
int qmin_id(int l, int r) {
  int k = log2(r - l);
  if (dp[0][l][k] < dp[0][r - (1 << k) + 1][k])
    return dp_id[0][l][k];
  else
    return dp_id[0][r - (1 << k) + 1][k];
}
int qmax_id(int l, int r) {
  int k = log2(r - l);
  if (dp[1][l][k] > dp[1][r - (1 << k) + 1][k])
    return dp_id[1][l][k];
  else
    return dp_id[1][r - (1 << k) + 1][k];
}
int main() {
  cin >> N >> Q;
  for (int u, v = 2; v <= N; v++) {
    cin >> u;
    adj[u].push_back(v);
  }
  depth[1] = 1;
  anc[1][0] = 1;
  dfs(1);
  for (int i = 1; i <= N; i++) {
    dp[0][i][0] = dp[1][i][0] = pre[i];
    dp_id[0][i][0] = dp_id[1][i][0] = i;
  }
  for (int j = 1; j <= 20; j++) {
    for (int i = 1; i <= N; i++) {
      if (i + (1 << (j - 1)) > N) break;
      if (dp[0][i][j - 1] < dp[0][i + (1 << (j - 1))][j - 1]) {
        dp[0][i][j] = dp[0][i][j - 1];
        dp_id[0][i][j] = dp_id[0][i][j - 1];
      } else {
        dp[0][i][j] = dp[0][i + (1 << (j - 1))][j - 1];
        dp_id[0][i][j] = dp_id[0][i + (1 << (j - 1))][j - 1];
      }
      if (dp[1][i][j - 1] > dp[1][i + (1 << (j - 1))][j - 1]) {
        dp[1][i][j] = dp[1][i][j - 1];
        dp_id[1][i][j] = dp_id[1][i][j - 1];
      } else {
        dp[1][i][j] = dp[1][i + (1 << (j - 1))][j - 1];
        dp_id[1][i][j] = dp_id[1][i + (1 << (j - 1))][j - 1];
      }
    }
  }
  int l, r, u, v, u1, u2, v1, v2;
  int x, y, z0, z1;
  while (Q--) {
    cin >> l >> r;
    u = qmin_id(l, r);
    v = qmax_id(l, r);
    x = u;
    y = v;
    if (u == l)
      u = qmin_id(u + 1, r);
    else if (u == r)
      u = qmin_id(l, u - 1);
    else {
      u1 = qmin_id(u + 1, r);
      u2 = qmin_id(l, u - 1);
      if (pre[u1] < pre[u2])
        u = u1;
      else
        u = u2;
    }
    z0 = lca(u, y);
    if (v == l)
      v = qmax_id(v + 1, r);
    else if (v == r)
      v = qmax_id(l, v - 1);
    else {
      v1 = qmax_id(v + 1, r);
      v2 = qmax_id(l, v - 1);
      if (pre[v1] > pre[v2])
        v = v1;
      else
        v = v2;
    }
    z1 = lca(x, v);
    if (depth[z0] > depth[z1])
      cout << x << " " << depth[z0] - 1 << endl;
    else
      cout << y << " " << depth[z1] - 1 << endl;
  }
  return 0;
}
