在 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$ $P_1 \ P_2 \ \dots \ P_N$ $M$ $A_1 \ B_1$ $A_2 \ B_2$ $\vdots$ $A_M \ B_M$

输出格式

输出一行到标准输出。如果可以将所有包裹投递到它们指定的邮局，输出最后一个包裹到达其指定邮局的最早可能时间。否则，输出 $-1$。

数据范围

• $2 \le N \le 200\,000$
• $1 \le M \le 200\,000$
• $1 \le P_i \le N \ (1 \le i \le N)$
• $1 \le A_j, B_j \le N \ (1 \le j \le M)$
• $A_j \neq B_j \ (1 \le j \le M)$
• 给定值均为整数。

子任务

1. (3 分) $N \le 3\,000$，$M = 1$。
2. (9 分) $N \le 3\,000$，$M \le 3\,000$。
3. (13 分) $P = (1, 1, 2, \dots, N - 1)$，且 $\max(B_1, B_2, \dots, B_M) < \min(A_1, A_2, \dots, A_M)$。
4. (25 分) $P = (1, 1, 2, \dots, N - 1)$。
5. (11 分) $P = (N, 1, 2, \dots, N - 1)$。
6. (25 分) $P_1 = 1$，$P_i < i \ (2 \le i \le N)$。
7. (14 分) 无附加限制。

样例

样例输入 1

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

样例输出 1

3

样例输入 2

3
2 1 3
1
1 3

样例输出 2

-1

样例输入 3

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

样例输出 3

5

样例输入 4

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

样例输出 4

4

样例输入 5

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

样例输出 5

5

样例输入 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