题目背景

译自 第24回日本情報オリンピック 本選 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}$。

否则输出一行一个整数，表示到达时间最晚的包裹的最早到达时刻。

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

3

3
2 1 3
1
1 3

-1

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

5

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

4

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

5

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

提示

样例解释

样例 $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$。
2. （9pts）$N\le 3,000$，$M\le 3,000$。
3. （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)$。
4. （25pts）$P=(1,1,2,\cdots,N-1)$。
5. （11pts）$P=(N,1,2,\cdots,N-1)$。
6. （25pts）$P_1=1$，$P_i\lt i$（$2\le i\le N$）。
7. （14pts）无额外限制。