#include <bits/stdc++.h>
using namespace std;
pair<int, int> ans;
const int N = 1e5 + 100;
int mem[N], h[N], par[N][20], Time, q, n, L, R;
pair<int, int> it[4 * N];
vector<int> a[N];
void home() {}
void update(int x, int i, int j, int u, int val) {
  if (i > u || j < u) return;
  if (i == u && j == i) {
    it[x] = {val, val};
    return;
  }
  int mid = (i + j) / 2;
  update(2 * x, i, mid, u, val);
  update(2 * x + 1, mid + 1, j, u, val);
  it[x].first = min(it[2 * x].first, it[2 * x + 1].first);
  it[x].second = max(it[2 * x].second, it[2 * x + 1].second);
}
void get(int x, int i, int j, int L, int R) {
  if (i > R || j < L) {
    return;
  }
  if (L <= i && j <= R) {
    ans.first = min(it[x].first, ans.first);
    ans.second = max(it[x].second, ans.second);
    return;
  }
  int mid = (i + j) / 2;
  get(2 * x, i, mid, L, R);
  get(2 * x + 1, mid + 1, j, L, R);
}
void dfs(int u) {
  ++Time;
  mem[Time] = u;
  update(1, 1, n, u, Time);
  for (int v : a[u]) {
    h[v] = h[u] + 1;
    par[v][0] = u;
    for (int i = 1; i <= 17; ++i) par[v][i] = par[par[v][i - 1]][i - 1];
    dfs(v);
  }
}
int LCA(int u, int v) {
  if (h[u] > h[v]) swap(u, v);
  int dist = h[v] - h[u];
  for (int i = 17; i >= 0; --i)
    if ((dist >> i) & 1) v = par[v][i];
  if (u == v) return u;
  for (int i = 17; i >= 0; --i) {
    if (par[u][i] != par[v][i]) u = par[u][i], v = par[v][i];
  }
  return par[u][0];
}
int cacl(int x, int L, int R) {
  ans = {n + 1, 0};
  int lca1 = 0, lca2 = 0;
  if (L <= x - 1)
    get(1, 1, n, L, x - 1), lca1 = LCA(mem[ans.first], mem[ans.second]);
  if (R >= x + 1) {
    ans = {n + 1, 0};
    get(1, 1, n, x + 1, R);
    lca2 = LCA(mem[ans.first], mem[ans.second]);
  }
  if (lca1 == 0) return h[lca2];
  if (lca2 == 0) return h[lca1];
  return h[LCA(lca1, lca2)];
}
int main() {
  home();
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> q;
  int u;
  for (int i = 2; i <= n; ++i) {
    cin >> u;
    a[u].push_back(i);
  }
  dfs(1);
  int x, y;
  for (int i = 1; i <= q; ++i) {
    cin >> L >> R;
    ans = {n + 1, 0};
    get(1, 1, n, L, R);
    x = mem[ans.first];
    y = mem[ans.second];
    int ok1 = cacl(x, L, R), ok3;
    ok3 = cacl(y, L, R);
    if (ok1 > ok3) {
      cout << x << " " << ok1 << '\n';
    } else {
      cout << y << " " << ok3 << '\n';
    }
  }
  return 0;
}
