#include <bits/stdc++.h>
using namespace std;
const int maxn=500005;
int read(){
	int ret=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while( isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch&15);ch=getchar();}
	return ret*f;
}
int n,m;
int ot[maxn],du[maxn],top[maxn],que[maxn],fa[maxn][20],len[maxn],dis[maxn];
bool vis[maxn];
void get(int now){
	if(top[now]) return ;
	if(!top[ot[now]]) get(ot[now]);
	top[now]=top[ot[now]];
	dis[now]=dis[ot[now]]+1;
	return ;
}
void Topo(){
	int hed=0,til=0;
	for(int i=1;i<=n;++i) if(!du[i]) que[++til]=i;
	while(hed<til){
		int now=que[++hed];
		if(!--du[ot[now]]){
			que[++til]=ot[now];
		}
	}
	for(int i=1;i<=n;++i){
		if(du[i]){
			top[i]=i;
			fa[i][0]=i;
		}else{
			fa[i][0]=ot[i];
		}
	}
	for(int i=1;i<=n;++i) if(!top[i]) get(i);
}
void DFS(int now,int fr,int d){
	if(now==fr){
		len[now]=d;
		return ;
	}
	dis[now]=d;top[now]=fr;
	vis[now]=1;
	DFS(ot[now],fr,d+1);
}
void solve(int u,int v){
	int fu=top[u],fv=top[v];
	if(fu==fv&&!vis[u]&&!vis[v]){
		int x=0,y=0;
		if(dis[u]>dis[v]){
			for(int t=19;~t;--t){
				if(vis[fa[u][t]]) continue;
				if(dis[fa[u][t]]>dis[v]){
					u=fa[u][t];
					x+=(1<<t);
				}
			}
			u=fa[u][0];
			x++;
		}
		if(dis[v]>dis[u]){
			for(int t=19;~t;--t){
				if(vis[fa[v][t]]) continue;
				if(dis[fa[v][t]]>dis[u]){
					v=fa[v][t];
					y+=(1<<t);
				}
			}
			v=fa[v][0];
			y++;
		}
		if(u==v){
			printf("%d %d\n",x,y);
			return ;
		}
		for(int t=19;~t;--t){
			if(fa[u][t]!=fa[v][t]){
				u=fa[u][t];x+=(1<<t);
				v=fa[v][t];y+=(1<<t);
			}
		}
		u=fa[u][0];x++;
		v=fa[v][0];y++; 
		printf("%d %d\n",x,y);
	}else{
		if(top[fu]!=top[fv]){
			printf("-1 -1\n");
			return ;
		}else{
			if(vis[u]) fu=u;
			if(vis[v]) fv=v;
			int x=0,y=0,wx=dis[fv]-dis[fu],wy=dis[fu]-dis[fv],t=top[fu];
			if(!vis[u]) x=dis[u];
			if(!vis[v]) y=dis[v];
			if(wx<0) wx+=len[t];
			if(wy<0) wy+=len[t];
			if(max(x+wx,y)<max(x,y+wy)){
				printf("%d %d\n",x+wx,y);
				return ;
			}
			if(max(x+wx,y)>max(x,y+wy)){
				printf("%d %d\n",x,y+wy);
				return ;
			}
			if(min(x+wx,y)<min(x,y+wy)){
				printf("%d %d\n",x+wx,y);
				return ;
			}
			if(min(x+wx,y)>min(x,y+wy)){
				printf("%d %d\n",x,y+wy);
				return ;
			}
			printf("%d %d\n",x+wx,y);
		}
	}
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n;++i){
		ot[i]=read();
		du[ot[i]]++;
	}
	Topo();
	for(int t=1;t<=19;++t){
		for(int i=1;i<=n;++i){
			fa[i][t]=fa[fa[i][t-1]][t-1];
		}	
	}
	for(int i=1;i<=n;++i){
		if(du[i]&&!vis[i]){
			vis[i]=1;
			DFS(ot[i],i,1);
		}
	}
	while(m--){
		int u=read(),v=read();
		solve(u,v);
	}	
	return 0;
}