郵便局(Post Office)

JOI 国にはN 個の郵便局があり,それぞれ1 からN までの番号が付けられている.各郵便局には「送り
先」が1 つだけ指定されており,郵便局i の送り先は郵便局Pi である.ただしPi = i である可能性もある.
もし時刻t に郵便局i から荷物を一つ発送した場合,時刻t + 1 に郵便局Pi にその荷物が到着する.ただ
し,荷物を発送している間はその郵便局から別の荷物を発送することができない.また,各郵便局には個数
の制限なく荷物を保管しておくことができる.
さて,これからJOI 国ではM 個の荷物を届けることになっている.j 個目の荷物は時刻0 に郵便局Aj に
到着し,最終的に指定の郵便局Bj に届けなければならない.郵便局と荷物の情報が与えられたとき,すべ
ての荷物を指定の郵便局に届けられるかを判定し,もし可能ならば最後に荷物が指定の郵便局に届く時刻と
して考えられる最も小さな値を求めるプログラムを作成せよ.

• 2 ≦N ≦200 000.
• 1 ≦M ≦200 000.
• 1 ≦Pi ≦N (1 ≦i ≦N).
• 1 ≦Aj, Bj ≦N (1 ≦j ≦M).
• Aj , Bj (1 ≦j ≦M).
• 入力はすべて整数である.

1. (3 点) N ≦3 000,M = 1.
2. (9 点) N ≦3 000,M ≦3 000.
3. (13 点) P = (1, 1, 2, · · · , N −1).また,max(B1, B2, . . . , BM) < min(A1, A2, . . . , AM) である.
4. (25 点) P = (1, 1, 2, · · · , N −1).
5. (11 点) P = (N, 1, 2, · · · , N −1).
6. (25 点) P1 = 1, Pi < i (2 ≦i ≦N).
7. (14 点) 追加の制約はない.

入力は以下の形式で標準入力から与えられる.
N
P1 P2 · · · PN
M
A1 B1
A2 B2
...
AM BM

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

第24 回日本情報オリンピック(JOI 2024/2025) 本選
2025 年2 月2 日(オンライン開催)

생성자가 기록되지 않았습니다.

출처 JOI 2025 Final