You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

题目译自 JOI 2025 Final T5 「郵便局 / 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$。

第二行包含用空格分隔的 $N$ 个整数 $P_1, P_2, \ldots P_N$。

第三行包含一个整数 $M$。

接下来 $M$ 行，每行包含两个用空格分隔的整数 $A_i,B_i$。

输出格式

如果可以将所有包裹递送到指定的邮局，输出最早的时刻值；否则，输出 $-1$。

5
1 1 2 3 4
3
3 2
3 1
3 1

3

可以通过以下方式可以在时刻 $3$ 之前将所有包裹递送到指定的邮局：

• 在时刻 $0$，邮局 $3$ 有包裹 $1,2,3$。将包裹 $2$ 发送到邮局 $2$。
• 在时刻 $1$，邮局 $2$ 有包裹 $2$，邮局 $3$ 有包裹 $1$ 和 $3$。从邮局 $2$ 发送包裹 $2$ 到邮局 $1$，并从邮局 $3$ 发送包裹 $3$ 到邮局 $2$。
• 在时刻 $2$，邮局 $1$ 有包裹 $2$，邮局 $2$ 有包裹 $3$，邮局 $3$ 有包裹 $1$。从邮局 $2$ 发送包裹 $3$ 到邮局 $1$，并从邮局 $3$ 发送包裹 $1$ 到邮局 $2$。
• 在时刻 $3$，邮局 $1$ 有包裹 $2$ 和 $3$，邮局 $2$ 有包裹 $1$，此时所有包裹都已到达指定的邮局。

因为无法在时刻 $2$ 之前将所有包裹递送到指定的邮局，因此输出 $3$。

这个样例满足子任务 $2,3,4,6,7$ 的限制。

3
2 1 3
1
1 3

-1

无论如何发送包裹，都无法从邮局 $1$ 将包裹送达邮局 $3$，因此输出 $-1$。

这个样例满足子任务 $1,2,7$ 的限制。

7
1 1 2 3 4 5 6
6
4 2
5 1
5 3
6 2
7 3
7 6

5

这个样例满足子任务 $2,4,6,7$ 的限制。

4
4 1 2 3
4
4 1
4 1
2 3
2 3

4

这个样例满足子任务 $2,5,7$ 的限制。

7
1 1 1 3 3 4 4
5
6 1
6 3
7 1
5 1
5 1

5

这个样例满足子任务 $2,6,7$ 的限制。

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

这个样例满足子任务 $2,7$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 200000$。
• $1 \leq M \leq 200000$。
• $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)$。
• 输入的所有值均为整数。

详细子任务附加限制及分值如下表所示。