#include <bits/stdc++.h>
#define F first
#define S second
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
const int MOD = 1e9 + 7;
const int LOG = 20;
vector< vi > adj;
vi level;
vi parent;
vector<bool> visited;
vector< vi > up;
vector< vi > lca_right;
vector< vi > lca_left;
int n;
void bfs(int src) {
queue<int> q;
q.push(src);
while(!q.empty()) {
int u = q.front();
visited[u] = true;
q.pop();
for(auto v: adj[u]) {
if(!visited[v]) {
level[v] = level[u] + 1;
parent[v] = u;
up[v][0] = u;
q.push(v);
}
}
}
}
void fill_up() {
for(int i = 1; i < LOG; ++i)
for(int j = 0; j < n; ++j)
if(up[j][i - 1] != -1)
up[j][i] = up[up[j][i - 1]][i - 1];
}
int walk(int u, int k) {
int node = u;
int ct = 0;
while(k) {
if(k % 2)
node = up[node][ct];
ct++;
if(ct > LOG)
return -1;
k /= 2;
}
return node;
}
int lca(int u, int v) {
if(level[u] > level[v])
swap(u, v);
int diff = abs(level[u] - level[v]);
v = walk(v, diff);
if(u == v)
return u;
while(1) {
int jump = 0;
for(int k = 0; k < LOG; ++k) {
if(up[u][k] == up[v][k])
break;
jump = k;
}
u = up[u][jump];
v = up[v][jump];
if(u == v)
return u;
}
}
vll two(LOG + 1, 1);
void fill_up_sparse() {
for(int i = 0; i < n; ++i) {
lca_right[i][0] = i;
lca_left[i][0] = i;
}
for(int i = 1; i <= LOG; ++i)
two[i] = two[i - 1] * 2ll;
for(int i = 1; i < LOG; ++i) {
for(int j = 0; j < n; ++j) {
if(lca_right[j][i - 1] != -1 and ((j + two[i - 1]) < n) and (lca_right[j + two[i - 1]][i - 1] != -1))
lca_right[j][i] = lca(lca_right[j][i - 1], lca_right[j + two[i - 1]][i - 1]);
}
}
for(int i = 1; i < LOG; ++i)
for(int j = n - 1; j >= 0; j--)
if(lca_left[j][i - 1] != -1 and (j - two[i - 1]) >= 0 and lca_left[j - two[i - 1]][i -1] != -1)
lca_left[j][i] = lca(lca_left[j][i - 1], lca_left[j - two[i - 1]][i -1]);
}
int lca_range(int l, int r) {
int len = 0;
for(int i = 0; i < LOG; ++i) {
if(l + two[i] > r)
break;
len = i;
}
// if(l == 0 and r == 8)
// cout << "***" << len << " " << lca_right[l][len] << " " << lca_left[r][len] << endl;
return lca(lca_right[l][len], lca_left[r][len]);
}
int main() {
std :: ios_base :: sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> n;
adj.assign(n, vi());
level.assign(n, 0);
parent.assign(n, -1);
visited.assign(n, false);
up.assign(n, vi(LOG, -1));
lca_left.assign(n, vi(LOG, -1));
lca_right.assign(n, vi(LOG, -1));
int q;
cin >> q;
int x, y;
for(int i = 2; i <= n; ++i) {
cin >> x;
y = i;
x--, y--;
adj[x].pb(y);
adj[y].pb(x);
}
bfs(0);
fill_up();
fill_up_sparse();
int l, r;
while(q--) {
cin >> l >> r;
l--, r--;
int low = l;
int high = r;
int lca_LR = lca_range(l, r);
int left = -1;
int right = -1;
while(low < high) {
int mid = low + (high - low + 1) / 2;
if(lca_range(l, mid) == lca_LR)
high = mid - 1;
else
low = mid;
}
if(lca_range(l, low) != lca_LR)
left = low;
if(left != -1 and left == r - 1) {
cout << r + 1 << " " << level[lca_range(l, left)] << endl;
continue;
}
low = l;
high = r;
while(low < high) {
int mid = low + (high - low) / 2;
if(lca_range(mid, r) == lca_LR)
low = mid + 1;
else
high = mid;
}
if(lca_range(low, r) != lca_LR)
right = low;
if(right != -1 and right == l + 1) {
cout << l + 1 << " " << level[lca_range(right, r)] << endl;
continue;
}
if(left + 1 == right - 1) {
cout << left + 2 << " " << level[lca(lca_range(l, left), lca_range(right, r))] << endl;
continue;
}
cout << l + 1 << " " << level[lca_LR] << endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgRiBmaXJzdAojZGVmaW5lIFMgc2Vjb25kCiNkZWZpbmUgcGIoeCkgcHVzaF9iYWNrKHgpCiNkZWZpbmUgbXAoYSwgYikgbWFrZV9wYWlyKGEsIGIpCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGxsOwp0eXBlZGVmIHBhaXI8aW50LCBpbnQ+IHBpaTsKdHlwZWRlZiB2ZWN0b3I8bGw+IHZsbDsKdHlwZWRlZiB2ZWN0b3I8aW50PiB2aTsKdHlwZWRlZiBwYWlyPGxsLCBsbD4gcGxsOwpjb25zdCBpbnQgTU9EID0gMWU5ICsgNzsKY29uc3QgaW50IExPRyA9IDIwOwp2ZWN0b3I8IHZpID4gYWRqOwp2aSBsZXZlbDsKdmkgcGFyZW50Owp2ZWN0b3I8Ym9vbD4gdmlzaXRlZDsKdmVjdG9yPCB2aSA+IHVwOwp2ZWN0b3I8IHZpID4gbGNhX3JpZ2h0Owp2ZWN0b3I8IHZpID4gbGNhX2xlZnQ7CmludCBuOwp2b2lkIGJmcyhpbnQgc3JjKSB7CglxdWV1ZTxpbnQ+IHE7CglxLnB1c2goc3JjKTsKCXdoaWxlKCFxLmVtcHR5KCkpIHsKCQlpbnQgdSA9IHEuZnJvbnQoKTsKCQl2aXNpdGVkW3VdID0gdHJ1ZTsKCQlxLnBvcCgpOwoJCWZvcihhdXRvIHY6IGFkalt1XSkgewoJCQlpZighdmlzaXRlZFt2XSkgewoJCQkJbGV2ZWxbdl0gPSBsZXZlbFt1XSArIDE7CgkJCQlwYXJlbnRbdl0gPSB1OwoJCQkJdXBbdl1bMF0gPSB1OwoJCQkJcS5wdXNoKHYpOwoJCQl9CgkJfQoJfQp9CnZvaWQgZmlsbF91cCgpIHsKCWZvcihpbnQgaSA9IDE7IGkgPCBMT0c7ICsraSkKCQlmb3IoaW50IGogPSAwOyBqIDwgbjsgKytqKQoJCQlpZih1cFtqXVtpIC0gMV0gIT0gLTEpCgkJCQl1cFtqXVtpXSA9IHVwW3VwW2pdW2kgLSAxXV1baSAtIDFdOwp9CmludCB3YWxrKGludCB1LCBpbnQgaykgewoJaW50IG5vZGUgPSB1OwoJaW50IGN0ID0gMDsKCXdoaWxlKGspIHsKCQlpZihrICUgMikKCQkJbm9kZSA9IHVwW25vZGVdW2N0XTsKCQljdCsrOwoJCWlmKGN0ID4gTE9HKQoJCQlyZXR1cm4gLTE7CgkJayAvPSAyOwoJfQoJcmV0dXJuIG5vZGU7Cn0KaW50IGxjYShpbnQgdSwgaW50IHYpIHsKCWlmKGxldmVsW3VdID4gbGV2ZWxbdl0pIAoJCXN3YXAodSwgdik7CglpbnQgZGlmZiA9IGFicyhsZXZlbFt1XSAtIGxldmVsW3ZdKTsKCXYgPSB3YWxrKHYsIGRpZmYpOwoJaWYodSA9PSB2KQoJCXJldHVybiB1OwoJd2hpbGUoMSkgewoJCWludCBqdW1wID0gMDsKCQlmb3IoaW50IGsgPSAwOyBrIDwgTE9HOyArK2spIHsKCQkJaWYodXBbdV1ba10gPT0gdXBbdl1ba10pCgkJCQlicmVhazsKCQkJanVtcCA9IGs7CgkJfQoJCXUgPSB1cFt1XVtqdW1wXTsKCQl2ID0gdXBbdl1banVtcF07CgkJaWYodSA9PSB2KQoJCQlyZXR1cm4gdTsKCX0KfQp2bGwgdHdvKExPRyArIDEsIDEpOwp2b2lkIGZpbGxfdXBfc3BhcnNlKCkgewoJZm9yKGludCBpID0gMDsgaSA8IG47ICsraSkgewoJCWxjYV9yaWdodFtpXVswXSA9IGk7CgkJbGNhX2xlZnRbaV1bMF0gPSBpOwoJfQoKCWZvcihpbnQgaSA9IDE7IGkgPD0gTE9HOyArK2kpCgkJdHdvW2ldID0gdHdvW2kgLSAxXSAqIDJsbDsKCglmb3IoaW50IGkgPSAxOyBpIDwgTE9HOyArK2kpIHsKCQlmb3IoaW50IGogPSAwOyBqIDwgbjsgKytqKSB7CgkJCWlmKGxjYV9yaWdodFtqXVtpIC0gMV0gIT0gLTEgYW5kICgoaiArIHR3b1tpIC0gMV0pIDwgbikgYW5kIChsY2FfcmlnaHRbaiArIHR3b1tpIC0gMV1dW2kgLSAxXSAhPSAtMSkpCgkJCQlsY2FfcmlnaHRbal1baV0gPSBsY2EobGNhX3JpZ2h0W2pdW2kgLSAxXSwgbGNhX3JpZ2h0W2ogKyB0d29baSAtIDFdXVtpIC0gMV0pOwoJCX0KCX0KCglmb3IoaW50IGkgPSAxOyBpIDwgTE9HOyArK2kpIAoJCWZvcihpbnQgaiA9IG4gLSAxOyBqID49IDA7IGotLSkgCgkJCWlmKGxjYV9sZWZ0W2pdW2kgLSAxXSAhPSAtMSBhbmQgKGogLSB0d29baSAtIDFdKSA+PSAwIGFuZCBsY2FfbGVmdFtqIC0gdHdvW2kgLSAxXV1baSAtMV0gIT0gLTEpCgkJCQlsY2FfbGVmdFtqXVtpXSA9IGxjYShsY2FfbGVmdFtqXVtpIC0gMV0sIGxjYV9sZWZ0W2ogLSB0d29baSAtIDFdXVtpIC0xXSk7Cn0KaW50IGxjYV9yYW5nZShpbnQgbCwgaW50IHIpIHsKCWludCBsZW4gPSAwOwoJZm9yKGludCBpID0gMDsgaSA8IExPRzsgKytpKSB7CgkJaWYobCArIHR3b1tpXSA+IHIpCgkJCWJyZWFrOwoJCWxlbiA9IGk7Cgl9CgkvLyBpZihsID09IDAgYW5kIHIgPT0gOCkKCS8vIAljb3V0IDw8ICIqKioiIDw8IGxlbiA8PCAiICIgPDwgbGNhX3JpZ2h0W2xdW2xlbl0gPDwgIiAiIDw8IGxjYV9sZWZ0W3JdW2xlbl0gPDwgZW5kbDsKCXJldHVybiBsY2EobGNhX3JpZ2h0W2xdW2xlbl0sIGxjYV9sZWZ0W3JdW2xlbl0pOwp9CmludCBtYWluKCkgewoJc3RkIDo6IGlvc19iYXNlIDo6IHN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CgljaW4udGllKE5VTEwpLCBjb3V0LnRpZShOVUxMKTsKCWNpbiA+PiBuOwoJYWRqLmFzc2lnbihuLCB2aSgpKTsKCWxldmVsLmFzc2lnbihuLCAwKTsKCXBhcmVudC5hc3NpZ24obiwgLTEpOwoJdmlzaXRlZC5hc3NpZ24obiwgZmFsc2UpOwoJdXAuYXNzaWduKG4sIHZpKExPRywgLTEpKTsKCWxjYV9sZWZ0LmFzc2lnbihuLCB2aShMT0csIC0xKSk7CglsY2FfcmlnaHQuYXNzaWduKG4sIHZpKExPRywgLTEpKTsKCWludCBxOwoJY2luID4+IHE7CglpbnQgeCwgeTsKCWZvcihpbnQgaSA9IDI7IGkgPD0gbjsgKytpKSB7CgkJY2luID4+IHg7CgkJeSA9IGk7CgkJeC0tLCB5LS07CgkJYWRqW3hdLnBiKHkpOwoJCWFkalt5XS5wYih4KTsKCX0KCWJmcygwKTsKCWZpbGxfdXAoKTsKCWZpbGxfdXBfc3BhcnNlKCk7CglpbnQgbCwgcjsKCXdoaWxlKHEtLSkgewoJCWNpbiA+PiBsID4+IHI7CgkJbC0tLCByLS07CgkJaW50IGxvdyA9IGw7CgkJaW50IGhpZ2ggPSByOwoJCWludCBsY2FfTFIgPSBsY2FfcmFuZ2UobCwgcik7CgkJaW50IGxlZnQgPSAtMTsKCQlpbnQgcmlnaHQgPSAtMTsKCQl3aGlsZShsb3cgPCBoaWdoKSB7CgkJCWludCBtaWQgPSBsb3cgKyAoaGlnaCAtIGxvdyArIDEpIC8gMjsKCQkJaWYobGNhX3JhbmdlKGwsIG1pZCkgPT0gbGNhX0xSKQoJCQkJaGlnaCA9IG1pZCAtIDE7CgkJCWVsc2UgCgkJCQlsb3cgPSBtaWQ7CgkJfQoJCWlmKGxjYV9yYW5nZShsLCBsb3cpICE9IGxjYV9MUikKCQkJbGVmdCA9IGxvdzsKCQlpZihsZWZ0ICE9IC0xIGFuZCBsZWZ0ID09IHIgLSAxKSB7CgkJCWNvdXQgPDwgciArIDEgPDwgIiAiIDw8IGxldmVsW2xjYV9yYW5nZShsLCBsZWZ0KV0gPDwgZW5kbDsKCQkJY29udGludWU7CgkJfQoJCWxvdyA9IGw7CgkJaGlnaCA9IHI7CgkJd2hpbGUobG93IDwgaGlnaCkgewoJCQlpbnQgbWlkID0gbG93ICsgKGhpZ2ggLSBsb3cpIC8gMjsKCQkJaWYobGNhX3JhbmdlKG1pZCwgcikgPT0gbGNhX0xSKQoJCQkJbG93ID0gbWlkICsgMTsKCQkJZWxzZQoJCQkJaGlnaCA9IG1pZDsKCQl9CgkJaWYobGNhX3JhbmdlKGxvdywgcikgIT0gbGNhX0xSKQoJCQlyaWdodCA9IGxvdzsKCQlpZihyaWdodCAhPSAtMSBhbmQgcmlnaHQgPT0gbCArIDEpIHsKCQkJY291dCA8PCBsICsgMSA8PCAiICIgPDwgbGV2ZWxbbGNhX3JhbmdlKHJpZ2h0LCByKV0gPDwgZW5kbDsKCQkJY29udGludWU7CgkJfQoJCWlmKGxlZnQgKyAxID09IHJpZ2h0IC0gMSkgewoJCQljb3V0IDw8IGxlZnQgKyAyIDw8ICIgIiA8PCBsZXZlbFtsY2EobGNhX3JhbmdlKGwsIGxlZnQpLCBsY2FfcmFuZ2UocmlnaHQsIHIpKV0gPDwgZW5kbDsKCQkJY29udGludWU7CQoJCX0KCQljb3V0IDw8IGwgKyAxIDw8ICIgIiA8PCBsZXZlbFtsY2FfTFJdIDw8IGVuZGw7Cgl9CglyZXR1cm4gMDsKfQo=