#include <bits/stdc++.h>
using namespace std;
void read_file(bool outToFile = 0) {
  freopen("in", "r", stdin);
  if (outToFile) freopen("out", "w", stdout);
}
int n, q;
vector<int> v[(100 * 1035)];
int in[(100 * 1035)];
int level[(100 * 1035)];
int anc[(100 * 1035)][20];
pair<int, int> mitree[3 * (100 * 1035)];
pair<int, int> matree[3 * (100 * 1035)];
int lcatree[3 * (100 * 1035)];
int counter = 1;
void dfs(int node, int p = -1, int lvl = 0) {
  anc[node][0] = p;
  in[node] = counter++;
  level[node] = lvl++;
  for (int i = 0; i < v[node].size(); i++) {
    if (v[node][i] == p) continue;
    dfs(v[node][i], node, lvl);
  }
}
void buildSpares() {
  for (int j = 1; j < 20; j++) {
    for (int i = 1; i <= n; i++) {
      int small_anc = anc[i][j - 1];
      if (small_anc == -1) {
        anc[i][j] = -1;
      } else
        anc[i][j] = anc[small_anc][j - 1];
    }
  }
}
void buildMin(int l = 1, int r = n, int id = 1) {
  if (l == r) {
    mitree[id] = make_pair(in[l], l);
    return;
  }
  int mid = (l + r) / 2;
  buildMin(l, mid, id * 2);
  buildMin(mid + 1, r, id * 2 + 1);
  mitree[id] = min(mitree[id * 2], mitree[id * 2 + 1]);
}
void buildMax(int l = 1, int r = n, int id = 1) {
  if (l == r) {
    matree[id] = make_pair(in[l], l);
    return;
  }
  int mid = (l + r) / 2;
  buildMax(l, mid, id * 2);
  buildMax(mid + 1, r, id * 2 + 1);
  matree[id] = max(matree[id * 2], matree[id * 2 + 1]);
}
int findLca(int a, int b) {
  if (level[a] > level[b]) swap(a, b);
  int lva = level[a], lvb = level[b];
  for (int bit = 19; bit >= 0; bit--) {
    if (lvb - (1 << bit) >= lva) {
      lvb -= (1 << bit);
      b = anc[b][bit];
    }
  }
  while (a != b) {
    int bit = -1;
    for (int i = 19; i >= 0; i--) {
      if (anc[a][i] != anc[b][i]) {
        bit = i;
        break;
      }
    }
    if (bit == -1) {
      a = b = anc[a][0];
    } else {
      a = anc[a][bit];
      b = anc[b][bit];
    }
  }
  return a;
}
void buildLca(int l = 1, int r = n, int id = 1) {
  if (l == r) {
    lcatree[id] = l;
    return;
  }
  int mid = (l + r) / 2;
  buildLca(l, mid, id * 2);
  buildLca(mid + 1, r, id * 2 + 1);
  lcatree[id] = findLca(lcatree[id * 2], lcatree[id * 2 + 1]);
}
pair<int, int> maxQuery(int x, int y, int l = 1, int r = n, int id = 1) {
  if (x <= l && r <= y) return matree[id];
  int mid = (l + r) / 2;
  if (mid >= y) return maxQuery(x, y, l, mid, id * 2);
  if (mid < x) return maxQuery(x, y, mid + 1, r, id * 2 + 1);
  return max(maxQuery(x, y, mid + 1, r, id * 2 + 1),
             maxQuery(x, y, l, mid, id * 2));
}
pair<int, int> minQuery(int x, int y, int l = 1, int r = n, int id = 1) {
  if (x <= l && r <= y) return mitree[id];
  int mid = (l + r) / 2;
  if (mid >= y) return minQuery(x, y, l, mid, id * 2);
  if (mid < x) return minQuery(x, y, mid + 1, r, id * 2 + 1);
  return min(minQuery(x, y, mid + 1, r, id * 2 + 1),
             minQuery(x, y, l, mid, id * 2));
}
int lcaQuery(int x, int y, int l = 1, int r = n, int id = 1) {
  if (x <= l && r <= y) return lcatree[id];
  int mid = (l + r) / 2;
  if (mid >= y) return lcaQuery(x, y, l, mid, id * 2);
  if (mid < x) return lcaQuery(x, y, mid + 1, r, id * 2 + 1);
  return findLca(lcaQuery(x, y, mid + 1, r, id * 2 + 1),
                 lcaQuery(x, y, l, mid, id * 2));
}
int main() {
  cin >> n >> q;
  for (int i = 2; i <= n; i++) {
    int x;
    scanf("%d", &x);
    v[x].push_back(i);
    v[i].push_back(x);
  }
  dfs(1);
  buildSpares();
  buildMin();
  buildMax();
  buildLca();
  while (q--) {
    int bestlvl = -1, bestid = -1;
    int l, r;
    scanf("%d%d", &l, &r);
    pair<int, int> tmp = maxQuery(l, r);
    int id = tmp.second;
    int lca;
    if (id == l) {
      lca = lcaQuery(l + 1, r);
      if (level[lca] > bestlvl) {
        bestid = id;
        bestlvl = level[lca];
      }
    } else if (id == r) {
      lca = lcaQuery(l, r - 1);
      if (level[lca] > bestlvl) {
        bestid = id;
        bestlvl = level[lcaQuery(l, r - 1)];
      }
    } else {
      lca = findLca(lcaQuery(l, id - 1), lcaQuery(id + 1, r));
      if (level[lca] > bestlvl) {
        bestid = id;
        bestlvl = level[lca];
      }
    }
    id = minQuery(l, r).second;
    if (id == l) {
      lca = lcaQuery(l + 1, r);
      if (level[lca] > bestlvl) {
        bestid = id;
        bestlvl = level[lca];
      }
    } else if (id == r) {
      lca = lcaQuery(l, r - 1);
      if (level[lca] > bestlvl) {
        bestid = id;
        bestlvl = level[lcaQuery(l, r - 1)];
      }
    } else {
      lca = findLca(lcaQuery(l, id - 1), lcaQuery(id + 1, r));
      if (level[lca] > bestlvl) {
        bestid = id;
        bestlvl = level[lca];
      }
    }
    cout << bestid << " " << bestlvl << endl;
  }
}
