Problems
In JOI country, there are N post offices numbered from 1 to N. Each post office i has an assigned “destination,” and the destination of post office i is post office P₍ᵢ₎ (note that it is possible for P₍ᵢ₎ to equal i).
If a package is sent from post office i at time t, it will arrive at post office P₍ᵢ₎ at time t + 1. However, a post office cannot send another package while it is in the process of sending a package (i.e. each post office can send at most one package per time unit). Each post office can store an unlimited number of packages at any given time.
Now, M packages need to be delivered in JOI country. The j-th package arrives at post office Aⱼ at time 0 and must eventually be delivered to the assigned post office Bⱼ.
Given the information about the post offices and the packages, write a program to determine whether it is possible to deliver all the packages to their assigned post offices. If so, output the smallest possible time at which the last package arrives at its destination; otherwise, output -1.
Input
The first line contains an integer N.
The second line contains N space-separated integers P₁, P₂, …, Pₙ.
The third line contains an integer M.
The next M lines each contain two space-separated integers Aⱼ and Bⱼ (1 ≤ Aⱼ, Bⱼ ≤ N) for j = 1, 2, …, M.
[Constrains]
2 ≤ N ≤ 200\ 000 1 ≤ M ≤ 200\ 000 1 \le P_i \le N (1 ≤ i ≤ N )1 ≤ A_j, B_j \le N (1 ≤ j ≤ M )A_j \ne B_j (1 ≤ j ≤ M )Given values are all integers.
Output
If it is possible to deliver all the packages to their assigned post offices, output a single line containing the smallest possible time at which the last package arrives at its destination.
Otherwise, output -1.
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 3 | N ≤ 3000, M = 1. |
| #2 | 9 | N ≤ 3000, M ≤ 3000 |
| #3 | 13 | P = (1, 1, 2, …, N − 1); max(B₁, B₂, …, B₍ᴹ₎) < min(A₁, A₂, …, A₍ᴹ₎ |
| #4 | 25 | P = (1, 1, 2, …, N − 1) |
| #5 | 11 | P = (N, 1, 2, …, N − 1) |
| #6 | 25 | P₁ = 1; P₍ᵢ₎ < i (2 ≤ i ≤ N) |
| #7 | 14 | No additional constraints |
Example #1
5
1 1 2 3 4
3
3 2
3 1
3 1
3
A feasible schedule delivering all packages by time 3 is as follows:
At time 0, packages 1, 2, and 3 are at post office 3. Send package 2 from post office 3 to post office 2.
At time 1, package 2 is at post office 2, and packages 1 and 3 remain at post office 3. Then, send package 2 from post office 2 to post office 1, and send package 3 from post office 3 to post office 2.
At time 2, package 2 is at post office 1, package 3 is at post office 2, and package 1 is still at post office 3. Next, send package 3 from post office 2 to post office 1, and send package 1 from post office 3 to post office 2.
At time 3, packages 2 and 3 are at post office 1, and package 1 is at post office 2. Thus, the last package arrives by time 3.
Example #2
3
2 1 3
1
1 3
-1
It is impossible to deliver a package from post office 1 to post office 3 with the given routes, so the output is -1.
Example #3
7
1 1 2 3 4 5 6
6
4 2
5 1
5 3
6 2
7 3
7 6
5
Example #4
4
4 1 2 3
4
4 1
4 1
2 3
2 3
4
Example #5
7
1 1 1 3 3 4 4
5
6 1
6 3
7 1
5 1
5 1
5
Example #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
You must sign in to write code.