#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int readint() {
  int x = 0, f = 1;
  char s = getchar();
  while (s < '0' || s > '9') {
    if (s == '-') f = -1;
    (s = getchar());
  }
  while (s >= '0' && s <= '9') {
    x = (x << 3) + (x << 1) + (s ^ 48);
    (s = getchar());
  }
  return x * f;
}
struct edge {
  int v, nxt;
  edge(){};
  edge(int V, int N) {
    v = V;
    nxt = N;
  }
} e[maxn << 1];
int head[maxn], edge_cnt = -1;
void addedge(int u, int v) {
  e[++edge_cnt] = edge(v, head[u]);
  head[u] = edge_cnt;
  e[++edge_cnt] = edge(u, head[v]);
  head[v] = edge_cnt;
}
int dep[maxn], fa[maxn][20];
int dfn[maxn], vis[maxn];
void dfs(int u, int pre) {
  dep[u] = dep[pre] + 1;
  fa[u][0] = pre;
  dfn[u] = ++dfn[0];
  vis[dfn[u]] = u;
  for (int j = 1; j <= 17; j++) {
    fa[u][j] = fa[fa[u][j - 1]][j - 1];
  }
  for (int i = head[u]; ~i; i = e[i].nxt) {
    int v = e[i].v;
    if (v == pre) continue;
    dfs(v, u);
  }
}
int LCA(int u, int v) {
  if (dep[u] > dep[v]) swap(u, v);
  for (int j = 17; j >= 0; j--) {
    if (dep[u] <= dep[fa[v][j]]) {
      v = fa[v][j];
    }
  }
  if (v == u) return u;
  for (int j = 17; j >= 0; j--) {
    if (fa[u][j] == fa[v][j]) continue;
    u = fa[u][j];
    v = fa[v][j];
  }
  return fa[u][0];
}
int maxx[maxn << 2], minx[maxn << 2];
void build(int x, int l, int r) {
  if (l == r) {
    maxx[x] = minx[x] = dfn[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(x << 1, l, mid);
  build(x << 1 | 1, mid + 1, r);
  maxx[x] = max(maxx[x << 1], maxx[x << 1 | 1]);
  minx[x] = min(minx[x << 1], minx[x << 1 | 1]);
}
int query1(int x, int l, int r, int goal_l, int goal_r) {
  if (goal_l > r || goal_r < l) return 0x3f3f3f3f;
  if (goal_l <= l && goal_r >= r) return minx[x];
  int mid = (l + r) / 2;
  return min(query1(x << 1, l, mid, goal_l, goal_r),
             query1(x << 1 | 1, mid + 1, r, goal_l, goal_r));
}
int query2(int x, int l, int r, int goal_l, int goal_r) {
  if (goal_l > r || goal_r < l) return 0;
  if (goal_l <= l && goal_r >= r) return maxx[x];
  int mid = (l + r) / 2;
  return max(query2(x << 1, l, mid, goal_l, goal_r),
             query2(x << 1 | 1, mid + 1, r, goal_l, goal_r));
}
int main() {
  memset(head, -1, sizeof(head));
  int n = readint(), q = readint();
  for (int i = 2; i <= n; i++) {
    int f = readint();
    addedge(f, i);
  }
  dfs(1, 0);
  build(1, 1, n);
  while (q--) {
    int x = readint(), y = readint();
    int l = query1(1, 1, n, x, y), r = query2(1, 1, n, x, y);
    l = vis[l], r = vis[r];
    int L = min(query1(1, 1, n, x, l - 1), query1(1, 1, n, l + 1, y));
    int R = max(query2(1, 1, n, x, r - 1), query2(1, 1, n, r + 1, y));
    L = vis[L], R = vis[R];
    int d1 = dep[LCA(L, r)], d2 = dep[LCA(l, R)];
    if (d1 > d2) {
      printf("%d %d\n", l, d1 - 1);
    } else {
      printf("%d %d\n", r, d2 - 1);
    }
  }
  return 0;
}
