OI XIX - ran

// https://szkopul.edu.pl/problemset/problem/gIvRmapl7sX6di87092Rmjdw/site/?key=statement

// Randka

#include <bits/stdc++.h>

// #define GARY_DBG
#define GARY_LIB

constexpr int sizik = 500 * 1001;
constexpr int sizik2 = 20;

#define ar std::array

typedef std::vector<std::vector<int>> _kra;

std::vector<int> kra[sizik];
int do_ktorego[sizik];

int n, k;

int sp[sizik];
int curr_sp = 1;
int visited[sizik];
int curr_vis = 1;
void DFS(int v) {
    if (visited[v] == curr_vis) {
        return;
    }
    visited[v] = curr_vis;
    sp[v] = curr_sp;
    for (const auto& u : kra[v]) {
        DFS(u);
    }
    DFS(do_ktorego[v]);
}

int drz[sizik], ck[sizik];
int ck_sz[sizik];
void DFS_cyk(int v) {
    if (visited[v] == curr_vis) {
        curr_vis++;
        int cnt = 0;
        do {
            drz[v] = v;
            ck[v] = cnt++;
            visited[v] = curr_vis;
            v = do_ktorego[v];
        } while (visited[v] != curr_vis);

        curr_vis++;
        do {
            ck_sz[v] = cnt;
            visited[v] = curr_vis;
            v = do_ktorego[v];
        } while (visited[v] != curr_vis);

        return;
    }
    visited[v] = curr_vis;
    DFS_cyk(do_ktorego[v]);
}

int depth[sizik];

int pre[sizik], post[sizik], timer;
int up[sizik][sizik2];

void DFS_drz_dzieci(int v, int p, int val, int d) {
    if (drz[v] != 0 && d > 0) return;
    depth[v] = d;
    drz[v] = val;
    pre[v] = ++timer;

    up[v][0] = p;
    for (int i = 1; i < sizik2; i++) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }

    for (const auto& u : kra[v]) {
        DFS_drz_dzieci(u, v, val, d + 1);
    }

    post[v] = ++timer;
}

bool is_ancestor(int u, int v) {
    return pre[u] <= pre[v] && post[u] >= post[v];
}

int lca(int u, int v) {
    assert(drz[u] == drz[v]);
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;
    for (int i = sizik2 - 1; i >= 0; i--) {
        if (!is_ancestor(up[u][i], v)) u = up[u][i];
    }
    return up[u][0];
}

std::pair<int, int> lca_dist(int a, int b) {
    int L = lca(a, b);
    return {depth[a] - depth[L], depth[b] - depth[L]};
}

int dl(int a, int b) {
    assert(sp[a] == sp[b]);
    assert(a == drz[a] && b == drz[b]);
    assert(ck_sz[a] == ck_sz[b]);
    if (ck[a] < ck[b]) {
        return ck[b] - ck[a];
    } else {
        return ck[b] - ck[a] + ck_sz[a];
    }
}

void drz_rest() {
    std::vector<int> good;
    for (int i = 1; i <= n; i++) {
        if (drz[i] > 0) {
            good.push_back(i);
        }
    }
    for (const auto& v : good) {
        assert(drz[v] == v);
        DFS_drz_dzieci(v, v, v, 0);
    }
}

void wyznacz_sp() {
    curr_vis++;
    for (int i = 1; i <= n; i++) {
        if (visited[i] != curr_vis) {
            DFS(i);
            curr_sp++;
        }
    }
}

int vis_sp[sizik];
void wyznacz_ck() {
    curr_vis++;
    for (int i = 1; i <= n; i++) {
        if (vis_sp[sp[i]] == 0) {
            DFS_cyk(i);
            vis_sp[sp[i]] = 1;
        }
    }
}

std::pair<int, int> get_best(const std::pair<int, int>& a, const std::pair<int, int>& b) {
    int m1 = std::max(a.first, a.second);
    int m2 = std::max(b.first, b.second);

    if (m1 < m2) {
        return a;
    } else if (m2 < m1) {
        return b;
    } else {
        m1 = std::min(a.first, a.second);
        m2 = std::min(b.first, b.second);

        if (m1 < m2) {
            return a;
        } else if (m2 < m1) {
            return b;
        } else {
            if (a.second < b.second) {
                return a;
            } else {
                return b;
            }
        }
    }

    return a;
}

void zapyt(int a, int b) {
    if (sp[a] != sp[b]) {
        std::cout << "-1 -1\n";
    } else if (drz[a] == drz[b]) {
        auto [da, db] = lca_dist(a, b);
        std::cout << da << " " << db << '\n';
    } else {
        int dx = depth[a], dy = depth[b];
        auto p1 = std::make_pair(dx + dl(drz[a], drz[b]), dy);
        auto p2 = std::make_pair(dx, dy + dl(drz[b], drz[a]));

        auto p = get_best(p1, p2);
        std::cout << p.first << " " << p.second << '\n';
    }
}

void solve() {
    std::cin >> n >> k;

    for (int i = 1; i <= n; i++) {
        std::cin >> do_ktorego[i];
        kra[do_ktorego[i]].push_back(i);
    }

    wyznacz_sp();
    wyznacz_ck();
    drz_rest();

    for (; k > 0; k--) {
        int a, b;
        std::cin >> a >> b;

        zapyt(a, b);
    }
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}