#P2791. [Poi2012]Rendezvous

    ID: 1899 传统题 2000ms 128MiB 尝试: 308 已通过: 138 难度: 7 上传者: 标签>CF2200提高功能图入度剥离基环树拆环LCA树上倍增有限候选集缩减鸣谢Oimaster

[Poi2012]Rendezvous

题目描述

给定一个 nn 个顶点的有向图,每个顶点有且仅有一条出边。

对于顶点 ii,记它的出边为 (i,ai)(i,a_i)。

再给出 qq 组询问,每组询问由两个顶点 a,ba,b 组成,要求输出满足下面条件的 x,yx,y:

  1. 从顶点 aa 沿着出边走 xx 步和从顶点 bb 沿着出边走 yy 步后到达的顶点相同。
  2. 在满足条件 11 的情况下 max⁡(x,y)\max(x,y) 最小。
  3. 在满足条件 11 和 22 的情况下 min⁡(x,y)\min(x,y) 最小。
  4. 在满足条件 1,21,2 和 33 的情况下 x≥yx\ge y。

如果不存在满足条件 11 的 x,yx,y,输出 -1 -1。

输入格式

第一行两个正整数 n,qn,q。 第二行 nn 个正整数 a1…na_{1\dots n}。 接下来 qq 行,每行两个数 a,ba,b 表示一组询问。

输出格式

共 qq 行,每行表示一个询问的答案。

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

数据规模与约定

对于 100%100\% 的数据,1≤n,q≤5×1051\leq n,q\leq 5\times 10^5,1≤a,b,ai≤n1\leq a,b,a_i\leq n。