logo AlgoBeat OnlineJudge
登录 注册

#102791. [BZOJ 2791] [Poi2012]Rendezvous

内存限制:128 MiB 时间限制:25000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

对于顶点 ,记它的出边为

再给出 组询问,每组询问由两个顶点 组成,要求输出满足下面条件的

  1. 从顶点 沿着出边走 步和从顶点 沿着出边走 步后到达的顶点相同。
  2. 在满足条件 的情况下 最小。
  3. 在满足条件 的情况下 最小。
  4. 在满足条件 的情况下

如果不存在满足条件 ,输出 -1 -1

输入格式

第一行两个正整数
第二行 个正整数
接下来 行,每行两个数 表示一组询问。

输出格式

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

样例

样例输入 #1

12 5
4 3 5 5 1 1 12 12 9 9 7 1
7 2
8 11
1 2
9 10
10 5

样例输出 #1

2 3
1 2
2 2
0 1
-1 -1

数据范围与提示

对于 的数据,