문제
JOI 나라에는 1번부터 N번까지 번호가 매겨진 우체국들이 있습니다. 각 우체국 i는 지정된 “목적지”를 가지고 있으며, 우체국 i의 목적지는 우체국 P₍ᵢ₎입니다. (단, P₍ᵢ₎ = i 인 경우도 있을 수 있습니다.)
만약 시간 t에 우체국 i에서 소포가 발송되면, 그 소포는 시간 t + 1에 우체국 P₍ᵢ₎에 도착합니다. 단, 우체국은 소포를 발송 중일 때 다른 소포를 동시에 발송할 수 없습니다. (즉, 각 우체국은 매 시간 단위마다 최대 한 개의 소포만 발송할 수 있습니다.) 또한, 각 우체국은 언제든지 무제한의 소포를 보관할 수 있습니다.
이제 JOI 나라에서 총 M개의 소포를 배달해야 합니다. j번째 소포는 시간 0에 우체국 Aⱼ에 도착하며, 최종적으로는 지정된 우체국 Bⱼ로 배달되어야 합니다.
우체국들과 소포들에 대한 정보가 주어질 때, 모든 소포를 그들의 지정된 우체국으로 배달하는 것이 가능한지 판단하고, 가능하다면 마지막 소포가 도착하는 가장 빠른 시간을 구하는 프로그램을 작성하세요. 만약 모든 소포를 배달하는 것이 불가능하다면, -1을 출력합니다.
입력
첫 번째 줄에 정수 N가 주어집니다.
두 번째 줄에는 N개의 정수 P₁, P₂, …, Pₙ이 공백으로 구분되어 주어집니다.
세 번째 줄에 정수 M이 주어집니다.
이후 M개의 줄 각각에 두 정수 Aⱼ와 Bⱼ (1 ≤ Aⱼ, Bⱼ ≤ N)가 공백으로 구분되어 주어집니다, for j = 1, 2, …, M.
[제약사항]
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 )주어진 값은 모두 정수입니다.
출력
모든 소포를 지정된 우체국으로 배달하는 것이 가능하면, 마지막 소포가 도착하는 가장 빠른 시간을 출력합니다.
불가능하면 -1을 출력합니다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #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점 | 추가 제약 조건 없음 |
예제 #1
5
1 1 2 3 4
3
3 2
3 1
3 1
3
다음과 같이 소포를 보내면, 모든 소포가 시간 3에 배달됩니다:
시간 0: 소포 1, 2, 3가 모두 우체국 3에 도착. 우체국 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 도착.
따라서 마지막 소포가 도착하는 시간은 3입니다.
예제 #2
3
2 1 3
1
1 3
-1
주어진 노선으로는 우체국 1에서 우체국 3으로 소포를 보내는 경로가 없으므로, 소포를 배달하는 것이 불가능합니다.
예제 #3
7
1 1 2 3 4 5 6
6
4 2
5 1
5 3
6 2
7 3
7 6
5
예제 #4
4
4 1 2 3
4
4 1
4 1
2 3
2 3
4
예제 #5
7
1 1 1 3 3 4 4
5
6 1
6 3
7 1
5 1
5 1
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
로그인해야 코드를 작성할 수 있어요.