#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100005;
const int inf = MAX_N + 10;
vector<int> adj[MAX_N];
int n, query;
int H[MAX_N];
pair<int, int> IT_max[4 * MAX_N], IT_min[4 * MAX_N];
int IT_lca[4 * MAX_N];
int a[MAX_N];
int Time = 0;
int F[MAX_N][20];
int fa[MAX_N];
void DFS(int u, int father, int curLen) {
  Time++;
  a[u] = Time;
  H[u] = curLen;
  F[u][0] = father;
  for (int i = 0; i < (int)adj[u].size(); i++) {
    int v = adj[u][i];
    if (v == father) {
      continue;
    }
    DFS(v, u, curLen + 1);
  }
}
void initLCA() {
  for (int k = 1; k < 20; k++) {
    for (int i = 1; i <= n; i++) {
      F[i][k] = F[F[i][k - 1]][k - 1];
    }
  }
}
int lca(int a, int b) {
  if (H[a] < H[b]) {
    swap(a, b);
  }
  for (int i = 19; i >= 0; i--) {
    if (H[a] - (1 << i) >= H[b]) {
      a = F[a][i];
    }
  }
  if (a == b) {
    return a;
  }
  for (int i = 19; i >= 0; i--) {
    if (F[a][i] && F[a][i] != F[b][i]) {
      a = F[a][i];
      b = F[b][i];
    }
  }
  return F[a][0];
}
void build(int index, int L, int R) {
  if (L > R) {
    return;
  }
  if (L == R) {
    IT_max[index] = make_pair(a[L], L);
    IT_min[index] = make_pair(a[L], L);
    IT_lca[index] = L;
    return;
  }
  int mid = (L + R) >> 1;
  build(2 * index, L, mid);
  build(2 * index + 1, mid + 1, R);
  IT_lca[index] = lca(IT_lca[2 * index], IT_lca[2 * index + 1]);
  int maxi = IT_max[2 * index].first;
  int id = IT_max[2 * index].second;
  if (maxi < IT_max[2 * index + 1].first) {
    maxi = IT_max[2 * index + 1].first;
    id = IT_max[2 * index + 1].second;
  }
  IT_max[index] = make_pair(maxi, id);
  int mini = IT_min[2 * index].first;
  id = IT_min[2 * index].second;
  if (mini > IT_min[2 * index + 1].first) {
    mini = IT_min[2 * index + 1].first;
    id = IT_min[2 * index + 1].second;
  }
  IT_min[index] = make_pair(mini, id);
}
pair<int, int> query_max(int index, int l, int r, int L, int R) {
  if (l > R || r < L) {
    return make_pair(-1, -1);
  }
  if (l <= L && R <= r) {
    return IT_max[index];
  }
  int mid = (L + R) >> 1;
  pair<int, int> val1 = query_max(2 * index, l, r, L, mid);
  pair<int, int> val2 = query_max(2 * index + 1, l, r, mid + 1, R);
  int maxi = val1.first;
  int id = val1.second;
  if (maxi < val2.first) {
    maxi = val2.first;
    id = val2.second;
  }
  return make_pair(maxi, id);
}
pair<int, int> query_min(int index, int l, int r, int L, int R) {
  if (l > R || r < L) {
    return make_pair(inf, -1);
  }
  if (l <= L && R <= r) {
    return IT_min[index];
  }
  int mid = (L + R) >> 1;
  pair<int, int> val1 = query_min(2 * index, l, r, L, mid);
  pair<int, int> val2 = query_min(2 * index + 1, l, r, mid + 1, R);
  int mini = val1.first;
  int id = val1.second;
  if (mini > val2.first) {
    mini = val2.first;
    id = val2.second;
  }
  return make_pair(mini, id);
}
int query_lca(int index, int l, int r, int L, int R) {
  if (l > R || r < L) {
    return -1;
  }
  if (l <= L && R <= r) {
    return IT_lca[index];
  }
  int mid = (L + R) >> 1;
  int x = query_lca(2 * index, l, r, L, mid);
  int y = query_lca(2 * index + 1, l, r, mid + 1, R);
  if (x == -1) {
    return y;
  } else if (y == -1) {
    return x;
  } else {
    return lca(x, y);
  }
}
void solve(int l, int r) {
  int u = query_max(1, l, r, 1, n).second;
  int v = query_min(1, l, r, 1, n).second;
  int res = u;
  int x1 = query_lca(1, l, u - 1, 1, n);
  int x2 = query_lca(1, u + 1, r, 1, n);
  int x;
  if (x1 == -1) {
    x = x2;
  } else if (x2 == -1) {
    x = x1;
  } else {
    x = lca(x1, x2);
  }
  int maxi = H[x];
  x1 = query_lca(1, l, v - 1, 1, n);
  x2 = query_lca(1, v + 1, r, 1, n);
  if (x1 == -1) {
    x = x2;
  } else if (x2 == -1) {
    x = x1;
  } else {
    x = lca(x1, x2);
  }
  if (maxi < H[x]) {
    res = v;
    maxi = H[x];
  }
  printf("%d %d\n", res, maxi);
}
int main() {
  scanf("%d %d", &n, &query);
  for (int i = 2; i <= n; i++) {
    int p;
    scanf("%d", &p);
    adj[p].push_back(i);
    adj[i].push_back(p);
  }
  DFS(1, -1, 0);
  initLCA();
  build(1, 1, n);
  while (query--) {
    int l, r;
    scanf("%d %d", &l, &r);
    solve(l, r);
  }
  return 0;
}
