AT_joi2025ho_e 郵便局 (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$ $P_1$ $P_2$ $\cdots$ $P_N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_M$ $B_M$

请输出一行到标准输出。如果所有包裹都能被送达到指定邮局，输出最后一个包裹到达目的地的最早时间，否则输出 `-1`。

## 子任务 1.（$3$ 分）$N \leq 3\,000$，$M = 1$。 2.（$9$ 分）$N \leq 3\,000$，$M \leq 3\,000$。 3.（$13$ 分）$P = (1, 1, 2, \cdots, N-1)$，且 $\max(B_1, B_2, \dots, B_M) < \min(A_1, A_2, \dots, A_M)$。 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$ 分）无额外限制。 --- ## 样例解释 1 例如，按照如下操作可以在时间 $3$ 前将所有包裹送达各自的目的地： - 在时间 $0$，包裹 $1$、$2$、$3$ 均在邮局 $3$。将包裹 $2$ 送到邮局 $2$。 - 在时间 $1$，包裹 $2$ 在邮局 $2$，包裹 $1$ 和 $3$ 仍在邮局 $3$。从邮局 $2$ 发包裹 $2$ 到邮局 $1$，从邮局 $3$ 发包裹 $3$ 到邮局 $2$。 - 在时间 $2$，包裹 $2$ 在邮局 $1$，包裹 $3$ 在邮局 $2$，包裹 $1$ 仍在邮局 $3$。从邮局 $2$ 发包裹 $3$ 到邮局 $1$，从邮局 $3$ 发包裹 $1$ 到邮局 $2$。 - 在时间 $3$，包裹 $2$ 和 $3$ 在邮局 $1$，包裹 $1$ 在邮局 $2$。此时所有包裹均已送达。 因为不可能更早完成所有包裹的传送，所以应输出 $3$。 本样例输入满足子任务 $2, 3, 4, 6, 7$ 的限制条件。 --- ## 样例解释 2 无论如何传送，都无法从邮局 $1$ 送包裹到邮局 $3$，所以输出 `-1`。 本样例输入满足子任务 $1, 2, 7$ 的限制条件。 --- ## 样例解释 3 本样例输入满足子任务 $2, 4, 6, 7$ 的限制条件。 --- ## 样例解释 4 本样例输入满足子任务 $2, 5, 7$ 的限制条件。 --- ## 样例解释 5 本样例输入满足子任务 $2, 6, 7$ 的限制条件。 --- ## 样例解释 6 本样例输入满足子任务 $2, 7$ 的限制条件。 # 数据范围 - $2 \leq N \leq 200\,000$。 - $1 \leq M \leq 200\,000$。 - $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$）。 - 所有输入均为整数。 由 ChatGPT 5 翻译