2691 「POI2012 R1」约会 Rendezvous

译自 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$.

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

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