题目描述

Byteasar is a ranger who works in the Arrow Cave - a famous rendezvous destination among lovers.

The cave consists of $n$ chambers connected with one-way corridors.

In each chamber exactly one outgoing corridor is marked with an arrow.

Every corridor leads directly to some (not necessarily different) chamber.

The enamoured couples that agree to meet in the Arrow Cave are notorious for forgetting to agree upon specific chamber, and consequently often cannot find their dates.

In the past this led to many mix-ups and misunderstandings\dots But ever since each chamber is equipped with an emergency telephone line to the ranger on duty, helping the enamoured find their dates has become the rangers' main occupation.

The rangers came up with the following method.

Knowing where the enamoured are, they tell each of them how many times they should follow the corridor marked with an arrow in order to meet their date.

The lovers obviously want to meet as soon as possible - after all, they came to the cave to spend time together, not to wander around alone!

Most rangers are happy to oblige: they do their best to give each couple a valid pair of numbers such that their maximum is minimal.

But some rangers, among their numbers Byteasar, grew tired of this extracurricular activity and ensuing puzzles. Byteasar has asked you to write a program that will ease the process. The program, given a description of the cave and the current location of $k$ couples, should determine $k$ pairs of numbers $x_i$ and $y_i$ such that if the $i$-th couple follows respectively: he $x_i$ and she $y_i$ corridors marked with arrows,then they will meet in a single chamber of the cave $max(x_i,y_i)$ is minimal,subject to above $min(x_i,y_i)$ is minimal,if above conditions do not determine a unique solution, then the woman should cover smaller distance ($x_i\ge y_i$).

It may happen that such numbers $x_i$ and $y_i$ do not exist - then let $x_i=y_i=-1$. Note that it is fine for several couples to meet in a single chamber. Once the lovers have found their dates, they will be happy to lose themselves in the cave again...

输入格式

In the first line of the standard input there are two positive integers $n$ and $k$($1\le n,k\le 500\ 000$), separated by a single space, that denote the number of chambers in the Arrow Cave and the number of couples who want to find their dates, respectively.

The chambers are numbered from 1 to $n$, while the enamoured couples are numbered from 1 to $k$.

The second line of input contains $n$ positive integers separated by single spaces:

the $i$-th such integer determines the number of chamber to which the corridor marked with an arrow going out of chamber $i$ leads.

The following $k$ lines specify the queries by the separated couples. Each such query consists of two positive integers separated by a single space - these denote the numbers of chambers where the lovers are - first him, then her.

In the tests worth 40% of the total points it additionally holds that $n,k\le 2\ 000$.

输出格式

Your program should print exactly $k$ lines to the standard output, one line per each couple specified in the input:

the $i$-th line of the output should give the instructions for the $i$-th couple on the input.

I.e., the $i$-th line of output should contain the integers $x_i,y_i$, separated by a single space.

题目大意

题目描述

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

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