3639. [POI 2012][BZOJ 2791]会合(Rendezvous)

【题目描述】

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

对于顶点 $i$，记它的出边为 $(i,to[i])$。

再给出 $q$ 组询问，每组询问由两个顶点 $a$、$b$ 组成，要求输出满足下面条件的 $x$、$y$：

$1$.从顶点 $a$ 沿着出边走 $x$ 步和从顶点 $b$ 沿着出边走 $y$ 步后到达的顶点相同。

$2$.在满足条件 $1$ 的情况下，如果解不唯一，则还需要令 $max(x,y)$ 最小。

$3$.在满足条件 $1$ 和 $2$ 的情况下，如果解不唯一，则还需要令 $min(x,y)$ 最小。

$4$.在满足条件 $1$、$2$ 和 $3$ 的情况下，如果解不唯一，则还需要令 $x≥y$。

如果不存在满足条件 $1$ 的 $x$、$y$，输出 $-1$。

【输入格式】

第一行两个正整数 $n$ 和 $q$。

第二行 $n$ 个正整数 $to[1],to[2],…,to[n]$。

下面 $q$ 行，每行两个正整数 $a$,$b$，表示一组询问。

【输出格式】

输出 $q$ 行，每行两个整数。

【样例输入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

【输入输出样例2/3】

输入输出样例2/3 

【数据规模与约定】

对于 $7$ 组数据，$1 \leq n \leq 15,1 \leq q \leq 10$;

对于另外 $7$ 组数据，$1 \leq n \leq 2000,1 \leq q \leq 2000$;

对于另外 $6$ 组数据，$1 \leq n \leq 100000,1 \leq q \leq 100000$;

对于 $100 \%$的数据，$1 \leq n,q \leq 500000,1 \leq to[i],a,b \leq n$;