#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=500005;
int n,q,to[N],a,b,lw[N],df[N],clk,ring[N],r,s[N],top,fa[N][22],bs[N],dep[N],pos[N],cnt[N];
bool vis[N];
vector<int> ns[N],fr[N];
char ch;
inline void read(int &x){x=0;ch=getchar();while(ch<48||ch>57)ch=getchar();while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch^48),ch=getchar();}
void tarjan(int cur)
{
	df[cur]=lw[cur]=++clk;
	s[++top]=cur;
	vis[cur]=1;
	if(!df[to[cur]]) tarjan(to[cur]),lw[cur]=min(lw[cur],lw[to[cur]]);
	else if(vis[cur]) lw[cur]=min(lw[cur],df[to[cur]]);
	if(df[cur]==lw[cur])
	{
		int x;
		++r;
		int k=0;
		do
		{
			x=s[top--];
			pos[x]=++k;
			vis[x]=0;
			ring[x]=r;
			ns[r].push_back(x);
		}while(x!=cur);
		cnt[r]=k;
	}
	return ;
}
void DFS(int cur,int lst,int rg)
{
	fa[cur][0]=lst;
	bs[cur]=rg;
	for(int i=1;i<=20;++i)
		fa[cur][i]=fa[fa[cur][i-1]][i-1];
	for(int i=0;i<fr[cur].size();++i)
		if(cnt[ring[fr[cur][i]]]<=1)
			dep[fr[cur][i]]=dep[cur]+1,DFS(fr[cur][i],cur,rg);
	return ; 
}
int LCA(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=20;i>=0;--i)
		if((1<<i)<=dep[x]-dep[y])
			x=fa[x][i];
	if(x==y) return x;
	for(int i=20;i>=0;--i)
		if(fa[x][i]!=fa[y][i])
			x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int main()
{
	freopen("rdz.in","r",stdin);
	freopen("rdz.out","w",stdout);
	read(n),read(q);
	for(int i=1;i<=n;++i)
	{
		read(to[i]);
		if(i!=to[i]) fr[to[i]].push_back(i);
	}
	for(int i=1;i<=n;++i)
		if(!df[i])
			tarjan(i);
	for(int i=1;i<=n;++i)
		if(i==to[i]||cnt[ring[i]]>1)
			DFS(i,0,i);
	for(int i=1;i<=q;++i)
	{
		read(a),read(b);
		if(ring[bs[a]]!=ring[bs[b]])
		{
			printf("-1 -1\n");
			continue;
		}
		if(bs[a]==bs[b])
		{
			int lca=LCA(a,b);
			printf("%d %d\n",dep[a]-dep[lca],dep[b]-dep[lca]);
		}
		else//ring
		{
			int disa,disb,da,db;
			if(pos[bs[a]]>pos[bs[b]]) disa=pos[bs[a]]-pos[bs[b]];
			else disa=pos[bs[a]]+cnt[ring[bs[a]]]-pos[bs[b]];
			disb=cnt[ring[bs[a]]]-disa;
			da=dep[a]-dep[bs[a]];
			db=dep[b]-dep[bs[b]];
			if(max(da+disa,db)!=max(db+disb,da))
			{
				if(max(da+disa,db)<=max(db+disb,da)) printf("%d %d\n",da+disa,db);
				else printf("%d %d\n",da,db+disb);
			}
			else if(min(da+disa,db)!=min(db+disb,da))
			{
				if(min(da+disa,db)<=min(db+disb,da)) printf("%d %d\n",da+disa,db);
				else printf("%d %d\n",da,db+disb);
			}
			else
			{
				if(da>=disb+db) printf("%d %d\n",da,disb+db);
				else printf("%d %d\n",da+disa,db);
			}
		}
	}
	return 0;
}