P11666 [JOI 2025 Final] 邮局 / Post Office

译自 [第24回日本情報オリンピック 本選](https://contests.ioi-jp.org/joi-ho-2025/index.html) T5。

有一张 $N$ 个节点 $N$ 条边的有向图，节点标号 $1\sim N$。 第 $i$ 条边从节点 $i$ 指向节点 $P_i$（注意，可能出现 $i=P_i$ 的情况），需要花 $1$ 单位时间经过它。 有 $M$ 个包裹，第 $j$（$1\le j\le M$）个包裹要从节点 $A_j$ 运到节点 $B_j$。这些包裹全部从 $0$ 时刻开始运送。 每条边一次只能运送一个包裹。节点可以存储无限多个包裹。 判断：是否能够将所有包裹都运到目的地。如果可以，还要求出到达时间最晚的包裹的最早到达时刻。

如下所示： > $N$ \ > $P_1$ $P_2$ $\cdots$ $P_N$\ > $M$\ > $A_1$ $B_1$\ > $A_2$ $B_2$\ > $\vdots$\ > $A_M$ $B_M$

如果无法运到，输出一行一个 $\texttt{-1}$。 否则输出一行一个整数，表示到达时间最晚的包裹的最早到达时刻。

### 样例解释 #### 样例 $1$ 解释 该样例满足子任务 $2,3,4,6,7$ 的限制。 #### 样例 $2$ 解释 该样例满足子任务 $1,2,7$ 的限制。 #### 样例 $3$ 解释 该样例满足子任务 $2,4,6,7$ 的限制。 #### 样例 $4$ 解释 该样例满足子任务 $2,5,7$ 的限制。 #### 样例 $5$ 解释 该样例满足子任务 $2,6,7$ 的限制。 #### 样例 $6$ 解释 该样例满足子任务 $2,7$ 的限制。 ### 数据范围 - $2\le N\le 2\times 10^5$。 - $1\le M\le 2\times 10^5$。 - $1\le P_i\le N$（$1\le i\le N$）。 - $1\le A_i,B_i\le N$（$1\le i\le M$）。 - $A_i\neq B_i$（$1\le i\le M$）。 - 输入的值全部是整数。 ### 子任务 1. （3pts）$N\le 3,000$，$M=1$。 1. （9pts）$N\le 3,000$，$M\le 3,000$。 1. （13pts）$P=(1,1,2,\cdots,N-1)$，$\max(B_1,B_2,\cdots,B_M)\lt \min(A_1,A_2,\cdots,A_M)$。 1. （25pts）$P=(1,1,2,\cdots,N-1)$。 1. （11pts）$P=(N,1,2,\cdots,N-1)$。 1. （25pts）$P_1=1$，$P_i\lt i$（$2\le i\le N$）。 7. （14pts）无额外限制。