#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int N, cnt, Q;
vector<int> graph[MAXN];
int counts[MAXN];
int parent[MAXN], level[MAXN], P[MAXN][21];
struct Node {
  int mx, mn, indmx, indmn;
  Node() {
    mx = INT_MIN;
    mn = INT_MAX;
    indmx = -1;
    indmn = -1;
  }
} Tree[4 * MAXN];
void dfs(int u, int p, int l) {
  level[u] = l;
  P[u][0] = p;
  counts[u] = ++cnt;
  for (int i = 0; i < graph[u].size(); i++) {
    int v = graph[u][i];
    if (v != p) {
      dfs(v, u, l + 1);
    }
  }
}
inline void merge(Node &ans, Node &left, Node &right) {
  if (left.mx > right.mx) {
    ans.mx = left.mx;
    ans.indmx = left.indmx;
  } else {
    ans.mx = right.mx;
    ans.indmx = right.indmx;
  }
  if (left.mn < right.mn) {
    ans.mn = left.mn;
    ans.indmn = left.indmn;
  } else {
    ans.mn = right.mn;
    ans.indmn = right.indmn;
  }
}
void build(int node, int start, int end) {
  if (start == end) {
    Tree[node].mx = Tree[node].mn = counts[start];
    Tree[node].indmx = Tree[node].indmn = start;
  } else {
    int mid = (start + end) / 2;
    build(2 * node, start, mid);
    build(2 * node + 1, mid + 1, end);
    merge(Tree[node], Tree[2 * node], Tree[2 * node + 1]);
  }
}
void update(int node, int start, int end, int l, int r, int val) {
  if (start > end || end < l || r < start) return;
  if (l <= start && end <= r) {
    if (val == -1) {
      Tree[node].indmx = Tree[node].indmn = -1;
      Tree[node].mx = INT_MIN;
      Tree[node].mn = INT_MAX;
    } else {
      Tree[node].mx = Tree[node].mn = val;
      Tree[node].indmx = Tree[node].indmn = start;
    }
    return;
  }
  int mid = (start + end) / 2;
  if (l <= mid) update(2 * node, start, mid, l, r, val);
  if (mid + 1 <= r) update(2 * node + 1, mid + 1, end, l, r, val);
  merge(Tree[node], Tree[2 * node], Tree[2 * node + 1]);
}
Node query(int node, int start, int end, int l, int r) {
  if (start > end || end < l || r < start) return Node();
  if (l <= start && end <= r) {
    return Tree[node];
  }
  int mid = (start + end) / 2;
  Node left = query(2 * node, start, mid, l, r);
  Node right = query(2 * node + 1, mid + 1, end, l, r);
  Node ans;
  merge(ans, left, right);
  return ans;
}
int LCA(int x, int y) {
  if (level[x] < level[y]) swap(x, y);
  int lg = log2(level[x]);
  for (int i = lg; i >= 0; i--) {
    if (level[x] - (1 << i) >= level[y]) {
      x = P[x][i];
    }
  }
  if (x == y) return x;
  for (int i = lg; i >= 0; i--) {
    if (P[x][i] != -1 && P[x][i] != P[y][i]) {
      x = P[x][i], y = P[y][i];
    }
  }
  return parent[x];
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> N >> Q;
  parent[1] = 1;
  for (int i = 2; i <= N; i++) {
    cin >> parent[i];
    graph[parent[i]].push_back(i);
  }
  for (int i = 0; 1 << i <= N; i++) {
    for (int j = 0; j <= N; j++) {
      P[j][i] = -1;
    }
  }
  cnt = 0;
  dfs(1, 1, 0);
  for (int i = 1; 1 << i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      if (P[j][i - 1] != -1) {
        P[j][i] = P[P[j][i - 1]][i - 1];
      }
    }
  }
  build(1, 1, N);
  int l, r;
  while (Q--) {
    cin >> l >> r;
    Node dum = query(1, 1, N, l, r);
    int mn = dum.indmn, mx = dum.indmx;
    int val = counts[mn];
    update(1, 1, N, mn, mn, -1);
    Node dum1 = query(1, 1, N, l, r);
    update(1, 1, N, mn, mn, val);
    val = counts[mx];
    update(1, 1, N, mx, mx, -1);
    Node dum2 = query(1, 1, N, l, r);
    update(1, 1, N, mx, mx, val);
    int lca1 = LCA(dum1.indmn, dum1.indmx);
    int lca2 = LCA(dum2.indmn, dum2.indmx);
    if (level[lca1] < level[lca2]) {
      cout << mx << " " << level[lca2] << endl;
    } else {
      cout << mn << " " << level[lca1] << endl;
    }
  }
}
