#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 100;
const int maxm = 5e5 + 10;
const long long INF = 1e18;
long long powmod(long long x, long long y) {
  long long t;
  for (t = 1; y; y >>= 1, x = x * x % mod)
    if (y & 1) t = t * x % mod;
  return t;
}
long long gcd(long long x, long long y) {
  if (y == 0) return x;
  return gcd(y, x % y);
}
int n, q;
vector<int> g[maxn];
int fa[maxn][20], dep[maxn], dfn[maxn], mp[maxn], tot = 0;
void dfs(int u, int f) {
  dep[u] = dep[f] + 1, fa[u][0] = f, dfn[u] = ++tot, mp[tot] = u;
  for (int(i) = (1); (i) < (20); (i)++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
  for (auto v : g[u])
    if (v ^ f) dfs(v, u);
}
int cnt = 0;
int root[maxn], ch[maxn * 20][2], val[maxn * 20];
void update(int old, int &cur, int l, int r, int pos) {
  cur = ++cnt;
  ch[cur][0] = ch[old][0], ch[cur][1] = ch[old][1];
  val[cur] = val[old] + 1;
  if (l == r) return;
  int mid = l + r >> 1;
  if (pos <= mid)
    update(ch[old][0], ch[cur][0], l, mid, pos);
  else
    update(ch[old][1], ch[cur][1], mid + 1, r, pos);
}
int query(int old, int cur, int l, int r, int k) {
  if (l == r) return mp[l];
  int tmp = val[ch[cur][0]] - val[ch[old][0]];
  int mid = l + r >> 1;
  if (tmp >= k)
    return query(ch[old][0], ch[cur][0], l, mid, k);
  else
    return query(ch[old][1], ch[cur][1], mid + 1, r, k - tmp);
}
int LCA(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  int tmp = dep[x] - dep[y];
  int i = 0;
  while ((1 << i) < tmp) i++;
  for (; i >= 0; i--)
    if (tmp & (1 << i)) x = fa[x][i];
  if (x == y) return x;
  for (i = 19; i >= 0; i--)
    if (fa[x][i] ^ fa[y][i]) x = fa[x][i], y = fa[y][i];
  return fa[x][0];
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> q;
  for (int(i) = (2); (i) < (n + 1); (i)++) {
    int x;
    cin >> x;
    g[x].push_back(i);
    g[i].push_back(x);
  }
  dfs(1, 1);
  for (int(i) = (1); (i) < (n + 1); (i)++) {
    update(root[i - 1], root[i], 1, n, dfn[i]);
  }
  for (int(i) = (0); (i) < (q); (i)++) {
    int x, y;
    cin >> x >> y;
    int tmp = y - x + 1, tx, ty;
    int ans1, ans2, ans3, ans4;
    int tp1 = query(root[x - 1], root[y], 1, n, 1),
        tp2 = query(root[x - 1], root[y], 1, n, tmp);
    ans1 = LCA(tp1, query(root[x - 1], root[y], 1, n, tmp - 1));
    ans2 = dep[ans1] - 1;
    ans3 = LCA(query(root[x - 1], root[y], 1, n, 2), tp2);
    ans4 = dep[ans3] - 1;
    if (ans2 > ans4)
      cout << tp2 << " " << ans2 << "\n";
    else
      cout << tp1 << " " << ans4 << "\n";
  }
  return 0;
}
