← 返回题目列表

AtCoder · joi2025ho_e

E. 邮局

中文机器翻译题面 查看原题

分数: 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).
  • 给定值均为整数。

子任务

  1. (3 点) N \leqq 3 \, 000, M = 1.
  2. (9 点) N \leqq 3 \, 000, M \leqq 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 \leqq i \leqq N).
  7. (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.