题目描述

给定一个$\red {n}$个顶点的有向图，每个顶点有且仅有一条出边。

对于顶点$\red {i}$，记它的出边为$\red {(i, a[i])}$。

再给出$\red {q}$组询问，每组询问由两个顶点$\red {a、b}$组成，要求输出满足下面条件的$\red {x、y}$：

1. 从顶点$\red {a}$沿着出边走$\red {x}$步和从顶点$\red b$沿着出边走$\red y$步后到达的顶点相同。
2. 在满足条件$\red {1}$的情况下$\red {max(x,y)}$最小。
3. 在满足条件$\red {1}$和$\red {2}$的情况下$\red {min(x,y)}$最小。
4. 在满足条件$\red {1、2}$和$\red 3$的情况下$\red {x>=y}$。

如果不存在满足条件$\red {1}$的$\red {x、y}$，输出$\red {-1 -1}$。

输入格式

第一行两个正整数$\red {n}$和$\red {q}$。

第二行$\red {n}$个正整数$\red {a[1],a[2],…,a[n]}$。

下面$\red {q}$行，每行两个正整数$\red {a,b}$，表示一组询问。

输出格式

输出$\red {q}$行，每行两个整数。

样例

输入样例

12 5
4 3 5 5 1 1 12 12 9 9 7 1
7 2
8 11
1 2
9 10
10 5

输出样例

2 3
1 2
2 2
0 1
-1 -1

提示

$\red {n,q≤500000}$,

$\red {a[i]≤n}$,

$\red {a,b≤n}$