分数: 100 点
问题陈述
在JOI国,有 N 邮局,编号自 1 to N.
每个邮局都有一个指定的“目的地”,以及邮局的目的地 i 是邮局 P_i。请注意,有可能 P_i = i.
如果包裹是从邮局寄出的 i 时间 t,它将到达邮局 P_i 时间 t + 1。但是,邮局在发送包裹的过程中无法发送另一个包裹。
每个邮局在任何给定时间都可以存储无限数量的包裹。
现在, M 包裹需要在 JOI 国家/地区投递。
的 j第一个包裹到达邮局 A_j 时间 0,并且最终必须交付到指定的邮局 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 代替。
约束
- 2 \leqq N \leqq 200 \, 000.
- 1 \leqq M \leqq 200 \, 000.
- 1 \leqq P_i \leqq N (1 \leqq i \leqq N).
- 1 \leqq A_j, B_j \leqq N (1 \leqq j \leqq M).
- A_j \neq B_j (1 \leqq j \leqq M).
- 给定值均为整数。
子任务
- (3 点) N \leqq 3 \, 000, M = 1.
- (9 点) N \leqq 3 \, 000, M \leqq 3 \,000.
- (13 点) P = (1, 1, 2, \cdots, N-1),和 \max(B_1, B_2, \dots, B_M) < \min(A_1, A_2, \dots, A_M).
- (25 点) P = (1, 1, 2, \cdots, N-1).
- (11 点) P = (N, 1, 2, \cdots, N-1).
- (25 点) P_1 = 1, P_i < i (2 \leqq i \leqq N).
- (14 点)没有额外的限制。
示例输入 1
5 1 1 2 3 4 3 3 2 3 1 3 1
示例输出 1
3
例如,通过以下方式发送包裹,所有包裹都可以按时送到指定的邮局 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。至此,所有包裹均已抵达目的地。
由于无法按时将所有包裹递送至指定的邮局 2,输出 3.
此示例输入满足子任务的约束 2, 3, 4, 6, 7.
示例输入 2
3 2 1 3 1 1 3
示例输出 2
-1
无论包裹如何寄出,都不可能从邮局投递包裹 1 到邮局 3,所以输出 -1.
此示例输入满足子任务的约束 1, 2, 7.
示例输入 3
7 1 1 2 3 4 5 6 6 4 2 5 1 5 3 6 2 7 3 7 6
示例输出 3
5
此示例输入满足子任务的约束 2, 4, 6, 7.
示例输入 4
4 4 1 2 3 4 4 1 4 1 2 3 2 3
示例输出 4
4
此示例输入满足子任务的约束 2, 5, 7.
示例输入 5
7 1 1 1 3 3 4 4 5 6 1 6 3 7 1 5 1 5 1
示例输出 5
5
此示例输入满足子任务的约束 2, 6, 7.
示例输入 6
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
6
此示例输入满足子任务的约束 2, 7.