#include <bits/stdc++.h>
using namespace std;
using namespace std;
vector<int> conn[100100];
int level[100100];
int par[100100][33];
bool vis[100100];
int visCount;
int in[100100];
void dfs(int curNode, int lvl) {
  level[curNode] = lvl;
  int len = conn[curNode].size();
  vis[curNode] = true;
  in[curNode] = ++visCount;
  for (int i = 0; i < len; i++) {
    if (!vis[conn[curNode][i]]) {
      dfs(conn[curNode][i], lvl + 1);
    }
  }
}
void build_lca_segment_tree_sparse_table(int n) {
  dfs(1, 0);
  par[1][0] = -1;
  for (int j = 1; j < 30; j++) {
    for (int i = 1; i <= n; i++) {
      if (par[i][j - 1] != -1) par[i][j] = par[par[i][j - 1]][j - 1];
    }
  }
}
int matchLevel(int u, int v) {
  for (int i = 30; i >= 0; i--) {
    if (par[u][i] != -1 && level[par[u][i]] >= level[v]) u = par[u][i];
  }
  return u;
}
int find_lca(int u, int v) {
  if (u == -1 || v == -1) return u + v + 1;
  if (level[u] > level[v])
    u = matchLevel(u, v);
  else if (level[v] > level[u])
    v = matchLevel(v, u);
  if (u == v) return u;
  for (int i = 30; i >= 0; i--) {
    if (par[u][i] != -1 && par[v][i] != -1 && par[u][i] != par[v][i]) {
      u = par[u][i];
      v = par[v][i];
    }
  }
  return par[u][0];
}
void init(int n = 100100 - 1) {
  memset(par, -1, sizeof(par));
  memset(vis, 0, sizeof(vis));
  for (int i = 0; i <= n; i++) {
    conn[i].clear();
  }
  visCount = 0;
}
int tree_lca[100100 << 2];
int build_lca_segment_tree(int node, int beg, int endd) {
  if (beg == endd) {
    return tree_lca[node] = beg;
  }
  int left = node << 1;
  int right = left | 1;
  int mid = (beg + endd) >> 1;
  tree_lca[node] = find_lca(build_lca_segment_tree(left, beg, mid),
                            build_lca_segment_tree(right, mid + 1, endd));
  return tree_lca[node];
}
int query_lca_segment_tree(int node, int beg, int endd, const int s,
                           const int f) {
  if (beg >= s && endd <= f) {
    return tree_lca[node];
  }
  if (beg > f || endd < s) return -1;
  int left = node << 1;
  int right = left | 1;
  int mid = (beg + endd) >> 1;
  return find_lca(query_lca_segment_tree(left, beg, mid, s, f),
                  query_lca_segment_tree(right, mid + 1, endd, s, f));
}
pair<int, int> tree_min_max_in[100100 << 2];
pair<int, int> build_ans_segment_tree(int node, int beg, int endd,
                                      const int n) {
  if (beg == endd) {
    return tree_min_max_in[node] = make_pair(beg, beg);
  }
  int left = node << 1;
  int right = left | 1;
  int mid = (beg + endd) >> 1;
  pair<int, int> left_del = build_ans_segment_tree(left, beg, mid, n);
  pair<int, int> right_del = build_ans_segment_tree(right, mid + 1, endd, n);
  tree_min_max_in[node].first =
      (in[left_del.first] < in[right_del.first] ? left_del.first
                                                : right_del.first);
  tree_min_max_in[node].second =
      (in[left_del.second] > in[right_del.second] ? left_del.second
                                                  : right_del.second);
  return tree_min_max_in[node];
}
pair<int, int> query_tree_min_max_in(int node, int beg, int endd, const int n,
                                     const int s, const int f) {
  if (beg >= s && endd <= f) {
    return tree_min_max_in[node];
  }
  if (beg > f || endd < s) {
    return make_pair(n + 1, 0);
  }
  int left = node << 1;
  int right = left | 1;
  int mid = (beg + endd) >> 1;
  pair<int, int> left_del = query_tree_min_max_in(left, beg, mid, n, s, f);
  pair<int, int> right_del =
      query_tree_min_max_in(right, mid + 1, endd, n, s, f);
  pair<int, int> p;
  p.first = (in[left_del.first] < in[right_del.first] ? left_del.first
                                                      : right_del.first);
  p.second = (in[left_del.second] > in[right_del.second] ? left_del.second
                                                         : right_del.second);
  return p;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  in[n + 1] = 1e9;
  init();
  for (int i = 2; i <= n; i++) {
    int u;
    cin >> u;
    par[i][0] = u;
    conn[i].push_back(u);
    conn[u].push_back(i);
  }
  build_lca_segment_tree_sparse_table(n);
  build_lca_segment_tree(1, 1, n);
  build_ans_segment_tree(1, 1, n, n);
  while (q--) {
    int l, r;
    cin >> l >> r;
    pair<int, int> del_node = query_tree_min_max_in(1, 1, n, n, l, r);
    int lll = find_lca(query_lca_segment_tree(1, 1, n, l, del_node.first - 1),
                       query_lca_segment_tree(1, 1, n, del_node.first + 1, r));
    int rrr = find_lca(query_lca_segment_tree(1, 1, n, l, del_node.second - 1),
                       query_lca_segment_tree(1, 1, n, del_node.second + 1, r));
    int ans_level, ans_node;
    if (level[lll] > level[rrr]) {
      ans_node = del_node.first;
      ans_level = level[lll];
    } else {
      ans_node = del_node.second;
      ans_level = level[rrr];
    }
    cout << ans_node << " " << ans_level << endl;
  }
  return 0;
}
