#include <bits/stdc++.h>
using namespace std;
long long int arr[200005];
long long int tree[800025];
void build(long long int node, long long int start, long long int endi) {
  if (start == endi) {
    tree[node] = arr[start];
  } else {
    long long int mid = (start + endi) / 2;
    build(2 * node, start, mid);
    build(2 * node + 1, mid + 1, endi);
    tree[node] = max(tree[2 * node], tree[2 * node + 1]);
  }
}
void update(long long int node, long long int start, long long int endi,
            long long int idx, long long int val) {
  if (start == endi) {
    arr[idx] = val;
    tree[node] = val;
  } else {
    long long int mid = (start + endi) / 2;
    if (start <= idx and idx <= mid) {
      update(2 * node, start, mid, idx, val);
    } else {
      update(2 * node + 1, mid + 1, endi, idx, val);
    }
    tree[node] = max(tree[2 * node], tree[2 * node + 1]);
  }
}
long long int query(long long int node, long long int start, long long int endi,
                    long long int l, long long int r) {
  if (r < start or endi < l) {
    return 0;
  }
  if (l <= start and endi <= r) {
    return tree[node];
  }
  long long int mid = (start + endi) / 2;
  long long int p1 = query(2 * node, start, mid, l, r);
  long long int p2 = query(2 * node + 1, mid + 1, endi, l, r);
  return max(p1, p2);
}
long long int arr2[200005];
long long int tree2[800025];
void build2(long long int node, long long int start, long long int endi) {
  if (start == endi) {
    tree2[node] = arr2[start];
  } else {
    long long int mid = (start + endi) / 2;
    build2(2 * node, start, mid);
    build2(2 * node + 1, mid + 1, endi);
    tree2[node] = min(tree2[2 * node], tree2[2 * node + 1]);
  }
}
void update2(long long int node, long long int start, long long int endi,
             long long int idx, long long int val) {
  if (start == endi) {
    arr2[idx] = val;
    tree2[node] = val;
  } else {
    long long int mid = (start + endi) / 2;
    if (start <= idx and idx <= mid) {
      update2(2 * node, start, mid, idx, val);
    } else {
      update2(2 * node + 1, mid + 1, endi, idx, val);
    }
    tree2[node] = min(tree2[2 * node], tree2[2 * node + 1]);
  }
}
long long int query2(long long int node, long long int start,
                     long long int endi, long long int l, long long int r) {
  if (r < start or endi < l) {
    return 10000000000;
  }
  if (l <= start and endi <= r) {
    return tree2[node];
  }
  long long int mid = (start + endi) / 2;
  long long int p1 = query2(2 * node, start, mid, l, r);
  long long int p2 = query2(2 * node + 1, mid + 1, endi, l, r);
  return min(p1, p2);
}
vector<long long int> graph[100005];
long long int t;
long long int node[1000005];
long long int dep[100005];
void dfs(long long int n) {
  arr2[n] = t;
  node[t] = n;
  t++;
  for (long long int i = 0; i < graph[n].size(); i++) {
    dfs(graph[n][i]);
  }
  arr[n] = t;
  node[t] = n;
  t++;
}
long long int lift[100005][22];
void dfs0(long long int n, long long int p) {
  lift[n][0] = p;
  for (long long int i = 1; i <= 17; i++) {
    lift[n][i] = lift[lift[n][i - 1]][i - 1];
  }
  for (long long int i = 0; i < graph[n].size(); i++) {
    dep[graph[n][i]] = dep[n] + 1;
    dfs0(graph[n][i], n);
  }
}
long long int tl, tr;
long long int dis;
long long int bin(long long int l, long long int r, long long int n) {
  if (l == r) {
    return l;
  }
  long long int x = (l + r) / 2;
  long long int y = n;
  for (long long int i = 17; i >= 0; i--) {
    if (x & (1 << i)) {
      y = lift[y][i];
    }
  }
  if ((arr2[y] <= tl) && (tr <= arr[y])) {
    return bin(l, x, n);
  } else {
    return bin(x + 1, r, n);
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long int n, q;
  t = 0;
  cin >> n >> q;
  for (long long int i = 2; i <= n; i++) {
    long long int z;
    cin >> z;
    graph[z].push_back(i);
  }
  dfs0(1, 0);
  dfs(1);
  build(1, 1, n);
  build2(1, 1, n);
  while (q--) {
    long long int l, r;
    cin >> l >> r;
    long long int mini = query2(1, 1, n, l, r);
    long long int maxi = query(1, 1, n, l, r);
    mini = node[mini];
    maxi = node[maxi];
    long long int ans = 0;
    long long int guy = 0;
    long long int kk;
    if (1) {
      long long int z1 = arr[maxi];
      long long int z2 = arr2[maxi];
      update(1, 1, n, maxi, 0);
      update2(1, 1, n, maxi, 1000000000);
      tl = query2(1, 1, n, l, r);
      tr = query(1, 1, n, l, r);
      update(1, 1, n, maxi, z1);
      update2(1, 1, n, maxi, z2);
      kk = l;
      if (l == maxi) {
        kk = r;
      }
      long long int v1 = bin(0, dep[kk], kk);
      v1 = dep[kk] - v1;
      if (ans <= v1) {
        ans = v1;
        guy = maxi;
      }
    }
    if (1) {
      maxi = mini;
      long long int z1 = arr[maxi];
      long long int z2 = arr2[maxi];
      update(1, 1, n, maxi, 0);
      update2(1, 1, n, maxi, 1000000000);
      tl = query2(1, 1, n, l, r);
      tr = query(1, 1, n, l, r);
      update(1, 1, n, maxi, z1);
      update2(1, 1, n, maxi, z2);
      kk = l;
      if (l == maxi) {
        kk = r;
      }
      long long int v1 = bin(0, dep[kk], kk);
      v1 = dep[kk] - v1;
      if (ans <= v1) {
        ans = v1;
        guy = maxi;
      }
    }
    cout << guy << " " << ans << "\n";
  }
}
