问题 S: Rendezvous
内存限制:128 MB
时间限制:5.000 S
评测方式:文本比较
命题人:
提交:1
解决:1
题目描述
给定一个n个顶点的有向图,每个顶点有且仅有一条出边。
对于顶点i,记它的出边为(i, a[i])。
再给出q组询问,每组询问由两个顶点a、b组成,要求输出满足下面条件的x、y:
- 从顶点a沿着出边走x步和从顶点b沿着出边走y步后到达的顶点相同。
- 在满足条件1的情况下max(x,y)最小。
- 在满足条件1和2的情况下min(x,y)最小。
- 在满足条件1、2和3的情况下x≥y。
如果不存在满足条件1的x、y,输出-1 -1。
输入
第一行两个正整数n和q (n,q≤500,000)
第二行n个正整数a[1],a[2],...,a[n] (a[i]≤n)
下面q行,每行两个正整数a,b(a,b≤n),表示一组询问。
第二行n个正整数a[1],a[2],...,a[n] (a[i]≤n)
下面q行,每行两个正整数a,b(a,b≤n),表示一组询问。
输出
输出q行,每行两个整数。
样例输入 复制
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