#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 100010;
const int MAXL = 17;
const int BSIZ = 315;
int N, Q;
vector<long long> V[MAXN];
int p[MAXN][17];
int depth[MAXN];
vector<pair<pair<long long, long long>, int> > queries;
pair<long long, long long> ans[MAXN];
int a, b;
int fw[MAXN];
int pre[MAXN], post[MAXN];
int reversepre[MAXN];
int cmp(pair<pair<long long, long long>, int> a,
        pair<pair<long long, long long>, int> b) {
  if (a.first.first / BSIZ == b.first.first / BSIZ)
    return a.first.second < b.first.second;
  return a.first.first / BSIZ < b.first.first / BSIZ;
}
void update(int x, int v) {
  for (; x <= N; x += x & (-x)) fw[x] += v;
}
int sum(int x) {
  int res = 0;
  for (; x; x -= x & (-x)) res += fw[x];
  return res;
}
int rng(int x, int y) { return sum(y) - sum(x - 1); }
void dfs(int x) {
  pre[x] = a;
  reversepre[a] = x;
  ++a;
  for (auto v : V[x]) {
    depth[v] = depth[x] + 1;
    dfs(v);
  }
  post[x] = a - 1;
}
int fp(int x, int h) {
  for (int i = 0; i < MAXL; ++i)
    if ((1 << i) & h) x = p[x][i];
  return x;
}
int find_item(int a, int b) {
  if (rng(a, b) == 0) {
    return -1;
  }
  while (b > a) {
    int mid = (a + b) / 2;
    if (rng(a, mid) == 0)
      a = mid + 1;
    else
      b = mid;
  }
  assert(rng(a, a) == 1);
  return reversepre[a];
}
int main() {
  cin >> N >> Q;
  memset(p, -1, sizeof(p));
  for (int i = 2; i <= N; ++i) {
    cin >> p[i][0];
    V[p[i][0]].emplace_back(i);
  }
  a = 1;
  dfs(1);
  for (int k = 1; k < MAXL; ++k) {
    for (int i = 2; i <= N; ++i) {
      if (p[i][k - 1] != -1) p[i][k] = p[p[i][k - 1]][k - 1];
    }
  }
  for (int i = 0; i < Q; ++i) {
    cin >> a >> b;
    if (a + 1 == b) {
      if (depth[a] > depth[b])
        ans[i] = make_pair(b, depth[a]);
      else
        ans[i] = make_pair(a, depth[b]);
    } else {
      queries.emplace_back(make_pair(make_pair(a, b), i));
    }
  }
  sort(queries.begin(), queries.end(), cmp);
  int l = 1;
  int r = 0;
  for (auto i : queries) {
    int tar_l = i.first.first;
    int tar_r = i.first.second;
    int len = tar_r - tar_l + 1;
    for (; r < tar_r; ++r) update(pre[r + 1], 1);
    for (; r > tar_r; --r) update(pre[r], -1);
    for (; l < tar_l; ++l) update(pre[l], -1);
    for (; l > tar_l; --l) update(pre[l - 1], 1);
    int lower_bound = 0;
    int upper_bound = depth[tar_l];
    while (upper_bound > lower_bound) {
      int mid = (lower_bound + upper_bound) / 2;
      int tar = fp(tar_l, mid);
      if (rng(pre[tar], post[tar]) >= len)
        upper_bound = mid;
      else
        lower_bound = mid + 1;
    }
    int lca_depth = lower_bound;
    int lca_res = depth[tar_l] - lower_bound;
    lower_bound = 0;
    upper_bound = depth[tar_l];
    while (upper_bound > lower_bound) {
      int mid = (lower_bound + upper_bound) / 2;
      int tar = fp(tar_l, mid);
      if (rng(pre[tar], post[tar]) >= len - 1)
        upper_bound = mid;
      else
        lower_bound = mid + 1;
    }
    ans[i.second].second = depth[tar_l] - lower_bound;
    ++tar_l;
    lower_bound = 0;
    upper_bound = depth[tar_l];
    while (upper_bound > lower_bound) {
      int mid = (lower_bound + upper_bound) / 2;
      int tar = fp(tar_l, mid);
      if (rng(pre[tar], post[tar]) >= len - 1)
        upper_bound = mid;
      else
        lower_bound = mid + 1;
    }
    int res = depth[tar_l] - lower_bound;
    if (res > ans[i.second].second) {
      ans[i.second] = make_pair(tar_l - 1, res);
      continue;
    }
    --tar_l;
    if (ans[i.second].second == lca_res) {
      ans[i.second].first = tar_r;
      continue;
    }
    int parent = fp(tar_l, lca_depth);
    int child = fp(tar_l, lca_depth - 1);
    update(pre[tar_l], -1);
    int t = find_item(pre[parent], pre[child] - 1);
    if (t == -1) t = find_item(post[child] + 1, post[parent]);
    update(pre[tar_l], 1);
    ans[i.second].first = t;
  }
  for (int i = 0; i < Q; ++i)
    cout << ans[i].first << ' ' << ans[i].second << '\n';
}
