在 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 翻译