题目描述

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

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

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

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

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

输入格式

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

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

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

输出格式

输出 $q$ 行，每行两个整数，表示对应的 $x$ 和 $y$。

样例

输入样例：

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

样例解释

图的结构（出边）： 1→4, 2→3, 3→5, 4→5, 5→1, 6→1, 7→12, 8→12, 9→9, 10→9, 11→7, 12→1

询问1：$a=7, b=2$

• 从7走：7→12→1→4→5→1...
  从2走：2→3→5→1→4→5...
• 公共点出现在走若干步后，最优解是走到点5时，7走了2步，2走了3步，输出 2 3

询问2：$a=8, b=11$

• 8→12→1→4→5... 11→7→12→1...
• 公共点出现在点12时，8走1步，11走2步，输出 1 2

询问3：$a=1, b=2$

• 1→4→5→1... 2→3→5→1...
• 公共点出现在点1时，1走2步（1→4→5→1），2走2步（2→3→5→1），输出 2 2

询问4：$a=9, b=10$

• 9自环（9→9） 10→9→9...
• 公共点出现在点9时，9走0步，10走1步，输出 0 1

询问5：$a=10, b=5$

• 10→9→9...（在环9中） 5→1→4→5...（在另一个环中）
• 这两个环不相交，没有公共可达点，输出 -1 -1

数据范围

• $n, q \le 500000$
• $a[i] \le n$
• 询问中 $a, b \le n$

时空限制

• 时间限制：2 秒
• 空间限制：64 MB