LCA 287 E

#include <bits/stdc++.h>

#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define watch(x) cout << (#x) <<  " : " << x << '\n'
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

using namespace std;

struct item {
    int min_val;
    int max_val;
    int min_id;
    int max_id;

    void init(int v, int pos) {
        min_val = max_val = v;
        min_id = max_id = pos;
    }
};

item merge(item a, item b) {
    item res;
    if (a.max_val > b.max_val)
        res.max_val = a.max_val, res.max_id = a.max_id;
    else
        res.max_val = b.max_val, res.max_id = b.max_id;
    if (a.min_val < b.min_val)
        res.min_val = a.min_val, res.min_id = a.min_id;
    else
        res.min_val = b.min_val, res.min_id = b.min_id;
    return res;
}

struct segtree {
    vector < item > t;
    int base, N;

    void init(vector<int>& a) {
        int n = (int)a.size();
        t.resize(4 * n);
        build(a, 1, 0, n - 1);
        N = n;
    }

    void build(vector<int>& a, int v, int tl, int tr) {
        if (tl == tr) {
            t[v].init(a[tl], tl);
            return;
        }
        int tm = (tl + tr) >> 1;
        build(a, v << 1, tl, tm);
        build(a, v << 1 | 1, tm + 1, tr);
        t[v] = merge(t[v << 1], t[v << 1 | 1]);
    }

    item get(int l, int r, int v, int tl, int tr) {
        if (tl > r || tr < l)
            return item{(int)2e9, (int)-2e9, -1, -1};
        if (l <= tl && tr <= r)
            return t[v];
        int tm = (tl + tr) >> 1;
        return merge(get(l, r, v << 1, tl, tm),
                     get(l, r, v << 1 | 1, tm + 1, tr));
    }

    item get(int l, int r) {
        if (l > r)
            return item{(int)2e9, (int)-2e9, -1, -1};
        return get(l, r, 1, 0, N - 1);
    }
};

const int N = 1e5 + 128;
const int LOG = 20;
int lift[N][LOG];
int depth[N];
int tin[N], tout[N];
vector <int> g[N];
int n, q;
int timer;
vector <int> order;

void dfs(int v, int d = 0, int p = 1) {
    order.push_back(v);
    tin[v] = timer++;
    depth[v] = d;

    lift[v][0] = p;
    for (int b = 1; b < LOG; b++)
        lift[v][b] = lift[lift[v][b-1]][b-1];

    for (auto to : g[v])
        if (to != p)
            dfs(to, d + 1, v);

    order.push_back(v);
    tout[v] = timer++;
}

void solve() {
    cin >> n >> q;
    for (int i = 2; i <= n; i++) {
        int x;
        cin >> x;
        g[i].push_back(x);
        g[x].push_back(i);
    }

    dfs(1);

    segtree tmin, tmax, thei;

    vector <int> ttin, ttout;
    for (int i = 0; i < n; i++)
        ttin.push_back(tin[i + 1]), ttout.push_back(tout[i + 1]);

    tmin.init(ttin);
    tmax.init(ttout);

    vector<int> heii;
    for (auto c : order)
        heii.push_back(depth[c]);

    thei.init(heii);

    while (q--) {
        int l, r;
        cin >> l >> r;

        l--; r--;

        auto t_min = tmin.get(l, r);
        auto t_max = tmax.get(l, r);

        int delete_left = t_min.min_id;
        int delete_right = t_max.max_id;

        int delete_ans = -1;
        int ans = -1;

        auto t_min_without_deleted_left = merge(tmin.get(l, delete_left - 1), tmin.get(delete_left + 1, r));
        auto t_max_without_deleted_right = merge(tmax.get(l, delete_right - 1), tmax.get(delete_right + 1, r));

        int without_left_ans, without_right_ans;

        if (t_min_without_deleted_left.min_val + 1 >= t_min_without_deleted_left.max_val)
            without_left_ans = thei.get(t_min_without_deleted_left.min_val, t_min_without_deleted_left.max_val).min_val + 1;
        else
            without_left_ans = thei.get(t_min_without_deleted_left.min_val + 1, t_min_without_deleted_left.max_val - 1).min_val;

        if (t_max_without_deleted_right.min_val + 1 >= t_max_without_deleted_right.max_val)
            without_right_ans = thei.get(t_max_without_deleted_right.min_val, t_max_without_deleted_right.max_val).min_val + 1;
        else
            without_right_ans = thei.get(t_max_without_deleted_right.min_val + 1, t_max_without_deleted_right.max_val - 1).min_val;

        if (ans < without_left_ans)
            ans = without_left_ans, delete_ans = delete_left;
        if (ans < without_right_ans)
            ans = without_right_ans, delete_ans = delete_right;

        cout << delete_ans + 1 << ' ' << ans - 1 << '\n';
    }
}

main() {
    boost;
    solve();
    return 0;
}