#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
int to[N],n,q,atox[N],btox[N];

int bfs(int x,int xt[])
{//x到其它点的最少步数 
	queue<int> q;
	q.push(x);
	xt[x]=0;
	while(!q.empty())
	{
		int f=q.front();q.pop();
		int nxt=to[f];
		if(xt[nxt]==-1)
		{
			xt[nxt]=xt[f]+1;
			q.push(nxt);
		}		
	}
}

int main()
{
	ios::sync_with_stdio(false);
	freopen("rdz.in","r",stdin);
	freopen("rdz.out","w",stdout);
    cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>to[i];
	for(int i=1;i<=q;i++)
	{
		int a,b;
		cin>>a>>b;
		memset(atox,-1,sizeof(atox));
		memset(btox,-1,sizeof(btox));
		bfs(a,atox);//a->x最少步数 
		bfs(b,btox);//b->x最少步数 
		int bestx=-1,besty=-1,k=1;
		for(k=1;k<=n;k++)
			if(atox[k]>=0 && btox[k]>=0)
			{
				bestx=atox[k] , besty=btox[k];//初始化 
				break;
			}
		for(int j=k;j<=n;j++)
		{//枚举x,y 
			if(atox[j]>=0 && btox[j]>=0)
			{//如果x,y均可达j 
				int x=atox[j] , y=btox[j];
				if(max(x,y) < max(bestx,besty))
					bestx=x , besty=y;
				if(min(x,y) < min(bestx,besty))
					bestx=x , besty=y;
				if(y==bestx && x==besty && x>=y)
					bestx=x , besty=y;	
			}
		}
		cout<<bestx<<' '<<besty<<endl;
	}
	return 0;
}