#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5 + 100000;
const int MAXLOG = 18;
int n, h[MAXN], fo[MAXN], p[MAXN], pl[4 * MAXN];
vector<vector<int>> table;
vector<int> t[MAXN], euler;
void dfs(int u = 0, int alt = 0) {
  fo[u] = euler.size();
  h[u] = alt;
  euler.push_back(u);
  for (const auto& v : t[u]) {
    dfs(v, 1 + alt);
    euler.push_back(u);
  }
}
void build() {
  int pot = 0;
  for (int i = 1; i < 4 * MAXN; ++i)
    if ((1 << pot) == i)
      pl[i] = pot++;
    else
      pl[i] = pl[i - 1];
  int columns = 1 + pl[euler.size()];
  table.assign(euler.size(), vector<int>(columns, -2));
  for (int i = (int)0; i < (int)euler.size(); ++i) table[i][0] = euler[i];
  for (int j = (int)1; j < (int)columns; ++j)
    for (int i = 0; i + (1 << j) - 1 < (int)euler.size(); ++i) {
      table[i][j] = table[i][j - 1];
      if (h[table[i + (1 << (j - 1))][j - 1]] < h[table[i][j]])
        table[i][j] = table[i + (1 << (j - 1))][j - 1];
    }
}
void lcabuild() {
  dfs();
  build();
}
int st_query(int i, int j) {
  if (i > j) swap(i, j);
  int len = j - i + 1, k = pl[len];
  int ans = table[i][k];
  if (h[table[i + len - (1 << k)][k]] < h[ans])
    ans = table[i + len - (1 << k)][k];
  return ans;
}
int query(int u, int v) { return st_query(fo[u], fo[v]); }
int st[MAXN][MAXLOG];
void buildst() {
  for (int i = (int)0; i < (int)n; ++i) st[i][0] = i;
  for (int len = 1; (1 << len) <= n; ++len)
    for (int i = 0; i + (1 << len) <= n; ++i)
      st[i][len] = query(st[i][len - 1], st[i + (1 << (len - 1))][len - 1]);
}
int lcarange(int l, int r) {
  if (l > r) return -1;
  int pot = pl[1 + r - l];
  return query(st[l][pot], st[1 + r - (1 << pot)][pot]);
}
pair<bool, int> canl(int l, int r, int min_alt) {
  int low = l, high = r, best = -1;
  while (low <= high) {
    int mid = (low + high) >> 1;
    if (h[lcarange(l, mid)] >= min_alt) {
      best = mid;
      low = 1 + mid;
    } else {
      high = mid - 1;
    }
  }
  if (best != -1) {
    int fh = lcarange(l, best);
    int sh = lcarange(best + 2, r);
    int lcanode = sh != -1 ? query(fh, sh) : fh;
    return {h[lcanode] >= min_alt, min(1 + best, r)};
  }
  return {false, -1};
}
pair<bool, int> canr(int l, int r, int min_alt) {
  int low = l, high = r, best = -1;
  while (low <= high) {
    int mid = (low + high) >> 1;
    if (h[lcarange(mid, r)] >= min_alt) {
      best = mid;
      high = mid - 1;
    } else {
      low = 1 + mid;
    }
  }
  if (best != -1) {
    int fh = lcarange(l, best - 2);
    int sh = lcarange(best, r);
    int lcanode = fh != -1 ? query(fh, sh) : sh;
    return {h[lcanode] >= min_alt, max(best - 1, l)};
  }
  return {false, -1};
}
pair<int, int> solve(int l, int r) {
  int low = 0, high = n, best = -1, bestalt = -1;
  while (low <= high) {
    int mid = (low + high) >> 1;
    auto k = canl(l, r, mid);
    if (k.first) {
      low = 1 + mid;
      bestalt = mid;
      best = k.second;
    } else {
      auto q = canr(l, r, mid);
      if (q.first) {
        low = 1 + mid;
        bestalt = mid;
        best = q.second;
      } else {
        high = mid - 1;
      }
    }
  }
  return {best, bestalt};
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int q;
  cin >> n >> q;
  for (int i = (int)1; i < (int)n; ++i) {
    cin >> p[i];
    t[--p[i]].push_back(i);
  }
  lcabuild();
  buildst();
  while (q--) {
    int l, r;
    cin >> l >> r;
    --l;
    --r;
    auto k = solve(l, r);
    cout << 1 + k.first << ' ' << k.second << '\n';
  }
  return 0;
}
