题目描述

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

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

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

• 从顶点 $a$ 沿着出边走 $x$ 步和从顶点$b$ 沿着出边走 $y$步后到达的顶点相同。
• 在满足条件 1 的情况下，如果解不唯一，则还需要令 $max(x,y$) 最小。
• 在满足条件 1 和 2 的情况下，如果解不唯一，则还需要令 $min(x,y)$ 最小。
• 在满足条件 1、2 和 3 的情况下，如果解不唯一，则还需要令 $x≥y$。

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

输入格式

第一行两个正整数 $n$和$q$。

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

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

输出格式

输出 $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

数据范围

$n,q≤500000,a[i]≤n,a,b≤n$

来源

• 算法竞赛进阶指南