#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long expo(long long base, long long pow) {
  long long ans = 1;
  while (pow != 0) {
    if (pow & 1 == 1) {
      ans = ans * base;
      ans = ans % mod;
    }
    base *= base;
    base %= mod;
    pow /= 2;
  }
  return ans;
}
long long inv(long long x) { return expo(x, mod - 2); }
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int M = 1e5 + 5;
vector<int> vec[M];
int par_original[M], level[M], ancestor[M][21], euler[M], whichNodeAtIndex[M];
int n;
int dexx = 1;
int segTree[2][4 * M];
int LARGE, SMALL;
void dfs(int u, int p, int lev, bool is_root) {
  euler[u] = dexx;
  whichNodeAtIndex[dexx] = u;
  dexx++;
  if (is_root) {
    lev = 0;
    p = -1;
  }
  level[u] = lev;
  par_original[u] = p;
  for (int i = 0; i < vec[u].size(); i++) {
    int v = vec[u][i];
    if (v == p) continue;
    dfs(v, u, lev + 1, 0);
  }
}
void preprocess() {
  memset(ancestor, -1, sizeof(ancestor));
  for (int i = 1; i <= n; i++) ancestor[i][0] = par_original[i];
  for (int j = 1; (1 << j) <= n; j++) {
    for (int i = 1; i <= n; i++) {
      if ((1 << j) > level[i]) continue;
      ancestor[i][j] = ancestor[ancestor[i][j - 1]][j - 1];
    }
  }
}
int LCA(int p, int q) {
  int a = level[p];
  int b = level[q];
  int lo;
  if (b > a) swap(p, q);
  for (lo = 0; (1 << lo) <= level[p]; lo++)
    ;
  lo--;
  for (int j = lo; j >= 0; j--) {
    if (level[p] - (1 << j) >= level[q]) {
      p = ancestor[p][j];
    }
  }
  if (p == q) return p;
  for (int j = lo; j >= 0; j--) {
    if ((ancestor[p][j] != -1) && (ancestor[p][j] != ancestor[q][j])) {
      p = ancestor[p][j];
      q = ancestor[q][j];
    }
  }
  return par_original[p];
}
void init(int root) {
  dfs(root, -1, 0, 1);
  preprocess();
}
void merge_node(int d, int node) {
  if (d == 0) {
    segTree[0][node] = min(segTree[0][2 * node], segTree[0][2 * node + 1]);
  } else {
    segTree[1][node] = max(segTree[1][2 * node], segTree[1][2 * node + 1]);
  }
}
void build(int node, int l, int r) {
  if (l > r) return;
  if (l == r) {
    segTree[0][node] = euler[l];
    segTree[1][node] = euler[l];
    return;
  }
  int mid = (l + r) / 2;
  build(2 * node, l, mid);
  build(2 * node + 1, mid + 1, r);
  for (int j = 0; j < 2; j++) {
    merge_node(j, node);
  }
}
int query(int node, int l, int r, int ql, int qr, int what) {
  if (l > r || l > qr || ql > qr || ql > r) {
    if (what == 0) {
      return LARGE;
    }
    return SMALL;
  }
  if (l >= ql && r <= qr) {
    return segTree[what][node];
  }
  int mid = (l + r) / 2;
  int a = query(2 * node, l, mid, ql, qr, what);
  int b = query(2 * node + 1, mid + 1, r, ql, qr, what);
  if (what == 0) return min(a, b);
  return max(a, b);
}
void update(int node, int l, int r, int pos, int val) {
  if (l > r || l > pos || pos > r) return;
  if (l >= pos && r <= pos) {
    segTree[0][node] = val;
    segTree[1][node] = val;
    return;
  }
  int mid = (l + r) / 2;
  update(2 * node, l, mid, pos, val);
  update(2 * node + 1, mid + 1, r, pos, val);
  for (int j = 0; j < 2; j++) {
    merge_node(j, node);
  }
}
int main() {
  scanf("%d", &(n));
  int q;
  scanf("%d", &(q));
  LARGE = n + 2;
  SMALL = -1;
  int u;
  for (int i = 2; i <= n; i++) {
    int v = i;
    scanf("%d", &(u));
    vec[u].push_back(v);
  }
  init(1);
  build(1, 1, n);
  while (q--) {
    int L, R;
    scanf("%d", &(L));
    scanf("%d", &(R));
    int minVal = query(1, 1, n, L, R, 0);
    int indexOfMin = whichNodeAtIndex[minVal];
    update(1, 1, n, indexOfMin, LARGE);
    int secondMinVal = query(1, 1, n, L, R, 0);
    int indexOfSecondMin = whichNodeAtIndex[secondMinVal];
    update(1, 1, n, indexOfMin, minVal);
    int maxVal = query(1, 1, n, L, R, 1);
    int indexOfMax = whichNodeAtIndex[maxVal];
    update(1, 1, n, indexOfMax, SMALL);
    int secondMaxVal = query(1, 1, n, L, R, 1);
    int indexOfSecondMax = whichNodeAtIndex[secondMaxVal];
    update(1, 1, n, indexOfMax, maxVal);
    int LCA_1 = LCA(indexOfMin, indexOfSecondMax);
    int LCA_1_depth = level[LCA_1];
    int LCA_2 = LCA(indexOfSecondMin, indexOfMax);
    int LCA_2_depth = level[LCA_2];
    int aps = max(LCA_1_depth, LCA_2_depth);
    if (LCA_1_depth > LCA_2_depth) {
      printf("%d %d\n", indexOfMax, aps);
    } else {
      printf("%d %d\n", indexOfMin, aps);
    }
  }
}
