[AdditionalFile2691.zip](file://AdditionalFile2691.zip?type=additional_file)

#2691. 「POI2012 R1」约会 Rendezvous

标签: 传统 | 时间限制: 2500 ms | 内存限制: 128 MiB |

题目描述

译自 POI 2012 Stage 1. 「Rendezvous」

给定一个有 $n$ 个顶点的有向图，每个顶点有且仅有一条出边。每次询问给出两个顶点 $a_i$ 和 $b_i$，求满足以下条件的 $x_i$ 和 $y_i$：

• 从顶点 $a_i$ 沿出边走 $x_i$ 步与从顶点 $b_i$ 沿出边走 $y_i$ 步到达的顶点相同。
• $\max(x_i, y_i)$ 最小。
• 满足以上条件的情况下 $\min(x_i, y_i)$ 最小。
• 如果以上条件没有给出一个唯一的解，则还需要满足 $x_i \ge y_i$.

如果不存在这样的 $x_i$ 和 $y_i$，则 $x_i = y_i = -1$.

输入格式

第一行两个正整数 $n$ 和 $k$（$1 \le n \le 500\ 000,1 \le k \le 500\ 000$），表示顶点数和询问个数。

接下来一行 $n$ 个正整数，第 $i$ 个数表示 $i$ 号顶点出边指向的顶点。

接下来 $k$ 行表示询问，每行两个整数 $a_i$ 和 $b_i$.

输出格式

对每组询问输出两个整数 $x_i$ 和 $y_i$.

样例

输入

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

数据范围与提示

对于 $40\%$ 的数据，$n \le 2000,k \le 2000$.

对于 $100\%$ 的数据，$1 \le n \le 500\ 000,1 \le k \le 500\ 000$.