题目描述

题目译自 JOI 2025 Final T5 「郵便局 / Post Office」

在 JOI 国有 $N$ 个邮局，每个邮局从 $1$ 到 $N$ 编号。每个邮局都有一个唯一的发送目的地，邮局 $i$ 的发送目的地是邮局 $P_i$。值得注意的是，$P_i$ 也可能等于 $i$。如果在时刻 $t$ 从邮局 $i$ 发送一个包裹，那么在时刻 $t+1$ 包裹将到达邮局 $P_i$。但是，在发送包裹的过程中，无法从该邮局发送其他包裹。此外，每个邮局可以无限制地存放包裹。

现在，JOI 国有 $M$ 个包裹需要递送。第 $j$ 个包裹在时刻 $0$ 到达邮局 $A_j$，最终必须递送到指定的邮局 $B_j$。给定邮局和包裹的信息，编写一个程序，判断是否可以将所有包裹递送到指定的邮局，如果可以，求出所有包裹到达指定邮局的最早时刻。

输入格式

第一行包含一个整数 $N$。

第二行包含用空格分隔的 $N$ 个整数 $P_1, P_2, \ldots P_N$。

第三行包含一个整数 $M$。

接下来 $M$ 行，每行包含两个用空格分隔的整数 $A_i,B_i$。

输出格式

如果可以将所有包裹递送到指定的邮局，输出最早的时刻值；否则，输出 $-1$。

5
1 1 2 3 4
3
3 2
3 1
3 1

3

可以通过以下方式可以在时刻 $3$ 之前将所有包裹递送到指定的邮局：

• 在时刻 $0$，邮局 $3$ 有包裹 $1,2,3$。将包裹 $2$ 发送到邮局 $2$。
• 在时刻 $1$，邮局 $2$ 有包裹 $2$，邮局 $3$ 有包裹 $1$ 和 $3$。从邮局 $2$ 发送包裹 $2$ 到邮局 $1$，并从邮局 $3$ 发送包裹 $3$ 到邮局 $2$。
• 在时刻 $2$，邮局 $1$ 有包裹 $2$，邮局 $2$ 有包裹 $3$，邮局 $3$ 有包裹 $1$。从邮局 $2$ 发送包裹 $3$ 到邮局 $1$，并从邮局 $3$ 发送包裹 $1$ 到邮局 $2$。
• 在时刻 $3$，邮局 $1$ 有包裹 $2$ 和 $3$，邮局 $2$ 有包裹 $1$，此时所有包裹都已到达指定的邮局。

因为无法在时刻 $2$ 之前将所有包裹递送到指定的邮局，因此输出 $3$。

这个样例满足子任务 $2,3,4,6,7$ 的限制。

3
2 1 3
1
1 3

-1

无论如何发送包裹，都无法从邮局 $1$ 将包裹送达邮局 $3$，因此输出 $-1$。

这个样例满足子任务 $1,2,7$ 的限制。

7
1 1 2 3 4 5 6
6
4 2
5 1
5 3
6 2
7 3
7 6

5

这个样例满足子任务 $2,4,6,7$ 的限制。

4
4 1 2 3
4
4 1
4 1
2 3
2 3

4

这个样例满足子任务 $2,5,7$ 的限制。

7
1 1 1 3 3 4 4
5
6 1
6 3
7 1
5 1
5 1

5

这个样例满足子任务 $2,6,7$ 的限制。

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

6

这个样例满足子任务 $2,7$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 200000$。
• $1 \leq M \leq 200000$。
• $1 \leq P_i \leq N$ $(1 \leq i \leq N)$。
• $1 \leq A_j, B_j \leq N$ $(1 \leq j \leq M)$。
• $A_j \neq B_j$ $(1 \leq j \leq M)$。
• 输入的所有值均为整数。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$3$	$N \leq 3000, M=1$
$2$	$9$	$N \leq 3000, M \leq 3000$
$3$	$13$	$P=(1,1,2, \cdots, N-1), \max \left(B_{1}, B_{2}, \ldots, B_{M}\right) < \min \left(A_{1}, A_{2}, \ldots, A_{M}\right)$
$4$	$25$	$P=(1,1,2, \cdots, N-1)$
$5$	$11$	$P=(N, 1,2, \cdots, N-1)$
$6$	$25$	$P_{1}=1, P_{i}<i$ $(2 \leq i \leq N)$
$7$	$14$	无附加限制