#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
long long n, t, v, fth[500005], d[500005], dep[500005], rt[500005], st[500005][20], id[500005], sz[500005], a, b;
vector <int> g[500005], ag[500005];
queue <int> q;
bool vis[500005];
map <int, int> mp;
int fnd(int nowi)
{
if (nowi == fth[nowi])
{
return nowi;
}
return fth[nowi] = fnd(fth[nowi]);
}
void unn(int x, int y)
{
fth[fnd(x)] = fnd(y);
}
void dfs1(int nowi)
{
for (int i = 1;i <= __lg(dep[nowi]);i++)
{
st[nowi][i] = st[st[nowi][i - 1]][i - 1];
}
for (int i = 0;i < ag[nowi].size();i++)
{
int v = ag[nowi][i];
if (!vis[v])
{
continue;
}
rt[v] = rt[nowi];
dep[v] = dep[nowi] + 1;
st[v][0] = nowi;
dfs1(v);
}
}
void dfs2(int nowi)
{
rt[nowi] = nowi;
dep[nowi] = 1;
bool flag = 1;
for (int i = 0;i < g[nowi].size();i++)
{
int v = g[nowi][i];
if (vis[v])
{
continue;
}
if (!sz[v])
{
sz[v] = sz[nowi] + 1;
id[v] = id[nowi] + 1;
dfs2(v);
flag = 0;
}
else if (sz[v] < sz[nowi])
{
sz[v] = sz[nowi];
dfs2(v);
flag = 0;
}
}
if (flag)
{
vis[nowi] = 1;
}
}
int lca(int a, int b)
{
if (dep[a] < dep[b])
{
swap(a, b);
}
for (int i = __lg(dep[a]);i >= 0;i--)
{
if (dep[st[a][i]] < dep[b])
{
continue;
}
a = st[a][i];
}
if (a == b)
{
return a;
}
for (int i = __lg(dep[a]);i >= 0;i--)
{
if (st[a][i] == st[b][i])
{
continue;
}
a = st[a][i];
b = st[b][i];
}
return st[a][0];
}
int main()
{
cin.tie(0)->ios::sync_with_stdio(false);
cout.tie(0);
cin >> n >> t;
for (int i = 1;i <= n;i++)
{
fth[i] = i;
}
for (int i = 1;i <= n;i++)
{
cin >> v;
g[i].emplace_back(v);
ag[v].emplace_back(i);
unn(i, v);
}
for (int i = 1;i <= n;i++)
{
if (!(d[i] = ag[i].size()))
{
vis[i] = 1;
q.push(i);
}
}
while (q.size())
{
int u = q.front();
q.pop();
for (int i = 0;i < g[u].size();i++)
{
int v = g[u][i];
if (!--d[v])
{
vis[v] = 1;
q.push(v);
}
}
}
for (int i = 1;i <= n;i++)
{
if (!vis[i])
{
rt[i] = i;
dep[i] = 1;
dfs1(i);
if (!sz[i])
{
sz[i] = 1;
dfs2(i);
}
}
}
while (t--)
{
cin >> a >> b;
if (fnd(a) != fnd(b))
{
cout << "-1 -1\n";
}
else if (rt[a] == rt[b])
{
int lcaab = lca(a, b);
cout << dep[a] - dep[lcaab] << " " << dep[b] - dep[lcaab] << "\n";
}
else
{
int ansa1 = dep[a] - 1 + (id[rt[b]] - id[rt[a]] + sz[rt[a]]) % sz[rt[a]], ansb1 = dep[b] - 1, ansa2 = dep[a] - 1, ansb2 = dep[b] - 1 + (id[rt[a]] - id[rt[b]] + sz[rt[a]]) % sz[rt[a]];
if (max(ansa1, ansb1) < max(ansa2, ansb2))
{
cout << ansa1 << " " << ansb1 << "\n";
}
else if (max(ansa1, ansb1) > max(ansa2, ansb2))
{
cout << ansa2 << " " << ansb2 << "\n";
}
else
{
if (min(ansa1, ansb1) < min(ansa2, ansb2))
{
cout << ansa1 << " " << ansb1 << "\n";
}
else if (min(ansa1, ansb1) > min(ansa2, ansb2))
{
cout << ansa2 << " " << ansb2 << "\n";
}
else
{
if (ansa1 >= ansb1)
{
cout << ansa1 << " " << ansb1 << "\n";
}
else
{
cout << ansa2 << " " << ansb2 << "\n";
}
}
}
}
}
cout << endl;
return 0;
}
rt