#include <bits/stdc++.h>
#pragma comment(linker, "/stack:225450978")
#pragma GCC optimize("Ofast")
using namespace std;
const long long Mod = 1000000007LL, INF = 1e9, LINF = 1e18;
const long double Pi = 3.141592653589793116, EPS = 1e-9,
                  Gold = ((1 + sqrt(5)) / 2);
long long keymod[] = {1000000007LL, 1000000009LL, 1000000021LL, 1000000033LL};
long long keyCount = sizeof(keymod) / sizeof(long long);
template <class T>
int getbit(T s, int i) {
  return (s >> i) & 1;
}
template <class T>
T onbit(T s, int i) {
  return s | (T(1) << i);
}
template <class T>
T offbit(T s, int i) {
  return s & (~(T(1) << i));
}
template <class T>
int cntbit(T s) {
  return __builtin_popcountll(s);
}
auto TimeStart = chrono::steady_clock::now();
auto TimeEnd = chrono::steady_clock::now();
void ControlIO(int argc, char* argv[]);
void TimerStart();
void TimerStop();
void Exit();
string cppstr_infile = "FILE.IN";
string cppstr_outfile = "FILE.OUT";
long long n, q, l, r;
vector<long long> p, d, Log2;
vector<vector<long long> > adj, Table, TableLCA;
void DFS(long long z, long long last) {
  if (z != 0) d[z] = d[last] + 1;
  for (auto t : adj[z]) {
    if (t == last) continue;
    DFS(t, z);
    Table[t].push_back(z);
  }
}
void PreprocessNormal() {
  Table.resize(n);
  d.resize(n, 0);
  DFS(0, -1);
  for (long long j = 1; j < 17; j++) {
    for (long long i = 0; i < n; i++) {
      if (Table[i].size() < j) continue;
      if (Table[Table[i][j - 1]].size() < j) continue;
      Table[i].push_back(Table[Table[i][j - 1]][j - 1]);
    }
  }
}
long long LCA(long long x, long long y) {
  if (x == y) return x;
  if (d[x] == d[y]) {
    long long id = 0, Init = min(Table[x].size(), Table[y].size() - 1);
    for (long long i = Init; i >= 0; i--) {
      if (Table[x][i] != Table[y][i]) {
        id = i;
        break;
      }
    }
    return LCA(Table[x][id], Table[y][id]);
  }
  if (d[x] < d[y]) {
    long long mul = 1, id = 0;
    while (d[x] < d[y] - mul * 2) {
      mul *= 2;
      id++;
    }
    return LCA(x, Table[y][id]);
  }
  if (d[x] > d[y]) {
    long long mul = 1, id = 0;
    while (d[y] < d[x] - mul * 2) {
      mul *= 2;
      id++;
    }
    return LCA(Table[x][id], y);
  }
}
void PreprocessTableLCA() {
  TableLCA.resize(n);
  for (long long i = 0; i < n; i++) TableLCA[i].push_back(i);
  for (long long j = 1; j < 17; j++) {
    for (long long i = 0; i < n; i++) {
      if (TableLCA[i].size() < j) continue;
      if (i + (1LL << (j - 1)) >= n) continue;
      if (TableLCA[i + (1LL << (j - 1))].size() < j) continue;
      TableLCA[i].push_back(
          LCA(TableLCA[i][j - 1], TableLCA[i + (1LL << (j - 1))][j - 1]));
    }
  }
}
long long LCASegment(long long L, long long R) {
  long long x = log2(R - L + 1);
  return LCA(TableLCA[L][x], TableLCA[R - (1LL << x) + 1][x]);
}
long long binsearch_prefix(long long L, long long R, long long Anc) {
  long long top = L, bot = R, ans = L;
  while (top <= bot) {
    long long mid = (top + bot) / 2;
    if (LCASegment(L, mid) == Anc) {
      ans = mid;
      bot = mid - 1;
    } else
      top = mid + 1;
  }
  return ans;
}
long long binsearch_suffix(long long L, long long R, long long Anc) {
  long long top = L, bot = R, ans = R;
  while (top <= bot) {
    long long mid = (top + bot) / 2;
    if (LCASegment(mid, R) == Anc) {
      ans = mid;
      top = mid + 1;
    } else
      bot = mid - 1;
  }
  return ans;
}
long long ProceedAnswer(long long L, long long R, long long x) {
  if (L < x && x < R) return LCA(LCASegment(L, x - 1), LCASegment(x + 1, R));
  if (L == x) return LCASegment(x + 1, R);
  return LCASegment(L, x - 1);
}
void Input() {
  cin >> n >> q;
  p.resize(n, -1);
  adj.resize(n);
  for (long long i = 1; i < n; i++) {
    cin >> p[i];
    p[i]--;
    adj[p[i]].push_back(i);
    adj[i].push_back(p[i]);
  }
}
void Solve() {
  PreprocessNormal();
  PreprocessTableLCA();
  while (q--) {
    cin >> l >> r;
    l--;
    r--;
    long long TotalLCA = LCASegment(l, r);
    long long l1 = binsearch_prefix(l, r, TotalLCA),
              r1 = binsearch_suffix(l, r, TotalLCA);
    long long LCA_l1 = ProceedAnswer(l, r, l1),
              LCA_r1 = ProceedAnswer(l, r, r1);
    if (d[LCA_l1] > d[LCA_r1])
      cout << l1 + 1 << " " << d[LCA_l1] << '\n';
    else
      cout << r1 + 1 << " " << d[LCA_r1] << '\n';
  }
}
int main(int argc, char* argv[]) {
  ControlIO(argc, argv);
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  Input();
  TimerStart();
  Solve();
  TimerStop();
  return 0;
}
void ControlIO(int argc, char* argv[]) {
  char* infile = new char[cppstr_infile.size() + 1];
  char* outfile = new char[cppstr_outfile.size() + 1];
  strcpy(infile, cppstr_infile.c_str());
  strcpy(outfile, cppstr_outfile.c_str());
}
void TimerStart() {}
void TimerStop() {}
void Exit() {
  TimerStop();
  exit(0);
}
