E - 郵便局 (Post Office) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

Score: 100 points

Problem Statement

In the JOI country, there are N post offices, numbered from 1 to N.
Each post office has an assigned "destination," and the destination of post office i is post office P_i. Note that it is possible for P_i = i.
If a package is sent from post office i at time t, it will arrive at post office P_i at time t + 1. However, a post office cannot send another package while it is in the process of sending a package.
Each post office can store an unlimited number of packages at any given time.

Now, M packages need to be delivered in the JOI country.
The j-th package arrives at post office A_j at time 0, and it must eventually be delivered to the assigned post office B_j.
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, and if so, find the smallest possible time at which the last package arrives at its assigned post office.

Input

Read the following data from the standard input.

N
P_1 P_2 \cdots P_N
M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

Output

Output a single line to the standard output. If it is possible to deliver all the packages to their assigned post offices, output the smallest possible time at which the last package arrives at its assigned post office. Otherwise, output -1 instead.

Constraints

  • 2 \leqq N \leqq 200 \, 000.
  • 1 \leqq M \leqq 200 \, 000.
  • 1 \leqq P_i \leqq N (1 \leqq i \leqq N).
  • 1 \leqq A_j, B_j \leqq N (1 \leqq j \leqq M).
  • A_j \neq B_j (1 \leqq j \leqq M).
  • Given values are all integers.

Subtasks

  1. (3 points) N \leqq 3 \, 000， M = 1.
  2. (9 points) N \leqq 3 \, 000， M \leqq 3 \,000.
  3. (13 points) P = (1, 1, 2, \cdots, N-1), and \max(B_1, B_2, \dots, B_M) < \min(A_1, A_2, \dots, A_M).
  4. (25 points) P = (1, 1, 2, \cdots, N-1).
  5. (11 points) P = (N, 1, 2, \cdots, N-1).
  6. (25 points) P_1 = 1, P_i < i (2 \leqq i \leqq N).
  7. (14 points) No additional constraints.

Sample Input 1

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

Sample Output 1

3

For example, by sending the packages in the following way, all the packages can be delivered to their assigned post offices by time 3:

  • At time 0, packages 1, 2, and 3 are at post office 3. Send package 2 to post office 2.
  • At time 1, package 2 is at post office 2, and packages 1 and 3 are at post office 3. From post office 2, send package 2 to post office 1, and from post office 3, send package 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 at post office 3. From post office 2, send package 3 to post office 1, and from post office 3, send package 1 to post office 2.
  • At time 3, packages 2 and 3 are at post office 1, and package 1 is at post office 2. At this point, all the packages have reached their destinations.

Since it is not possible to deliver all the packages to their assigned post offices by time 2, output 3.

This sample input satisfies the constraints of Subtasks 2, 3, 4, 6, 7.

Sample Input 2

3
2 1 3
1
1 3

Sample Output 2

-1

No matter how the packages are sent, it is impossible to deliver a package from post office 1 to post office 3, so output -1.

This sample input satisfies the constraints of Subtasks 1, 2, 7.

Sample Input 3

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

Sample Output 3

5

This sample input satisfies the constraints of Subtasks 2, 4, 6, 7.

Sample Input 4

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

Sample Output 4

4

This sample input satisfies the constraints of Subtasks 2, 5, 7.

Sample Input 5

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

Sample Output 5

5

This sample input satisfies the constraints of Subtasks 2, 6, 7.

Sample Input 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

Sample Output 6

6

This sample input satisfies the constraints of Subtasks 2, 7.

配点： 100 点

問題文

JOI 国には N 個の郵便局があり，それぞれ 1 から N までの番号が付けられている． 各郵便局には「送り先」が 1 つだけ指定されており，郵便局 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 \cdots P_N
M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

標準出力に 1 行で出力せよ． すべての荷物を指定の郵便局に届けられる場合は，最後に荷物が指定の郵便局に届く時刻として考えられる最も小さな値を出力せよ． そうでない場合は，代わりに -1 を出力せよ．

制約

  • 2 \leqq N \leqq 200\,000．
  • 1 \leqq M \leqq 200\,000．
  • 1 \leqq P_i \leqq N (1 \leqq i \leqq N)．
  • 1 \leqq A_j, B_j \leqq N (1 \leqq j \leqq M)．
  • A_j \neq B_j (1 \leqq j \leqq M)．
  • 入力はすべて整数である．

小課題

  1. (3 点) N \leqq 3 \,000， M = 1．
  2. (9 点) N \leqq 3 \,000， M \leqq 3 \,000．
  3. (13 点) P = (1, 1, 2, \cdots, N-1)．また，\max(B_1, B_2, \dots, B_M) < \min(A_1, A_2, \dots, A_M) である．
  4. (25 点) P = (1, 1, 2, \cdots, N-1)．
  5. (11 点) P = (N, 1, 2, \cdots, N-1)．
  6. (25 点) P_1 = 1，P_i < i (2 \leqq i \leqq N)．
  7. (14 点) 追加の制約はない．

入力例 1

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

出力例 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 の制約を満たす．

入力例 2

3
2 1 3
1
1 3

出力例 2

-1

どのような送り方をしても郵便局 1 から郵便局 3 へ荷物を運ぶことはできないため，-1 を出力する．

この入力例は小課題 1,2,7 の制約を満たす．

入力例 3

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

出力例 3

5

この入力例は小課題 2,4,6,7 の制約を満たす．

入力例 4

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

出力例 4

4

この入力例は小課題 2,5,7 の制約を満たす．

入力例 5

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

出力例 5

5

この入力例は小課題 2,6,7 の制約を満たす．

入力例 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

この入力例は小課題 2,7 の制約を満たす．