郵便局 (Post Office)
日本語
Language
Contribute a translation- Time limit
- 2000 ms
- Memory limit
- 1024 MB
- Submissions
- 0
- Correct
- 0
- Solved by
- 0
- AC rate
- —
Statement
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\) に届けなければならない． 郵便局と荷物の情報が与えられたとき，すべての荷物を指定の郵便局に届けられるかを判定し，もし可能ならば最後に荷物が指定の郵便局に届く時刻として考えられる最も小さな値を求めるプログラムを作成せよ．
Input
入力は以下の形式で標準入力から与えられる．
\(N\)
\(P_1\) \(P_2\) \(\cdots\) \(P_N\)
\(M\)
\(A_1\) \(B_1\)
\(A_2\) \(B_2\)
\(\vdots\)
\(A_M\) \(B_M\)
Output
標準出力に \(1\) 行で出力せよ．
すべての荷物を指定の郵便局に届けられる場合は，最後に荷物が指定の郵便局に届く時刻として考えられる最も小さな値を出力せよ．
そうでない場合は，代わりに -1 を出力せよ．
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\))．
- 入力はすべて整数である．
Subtasks
- (\(3\) 点) \(N \leqq 3 \,000\)， \(M = 1\)．
- (\(9\) 点) \(N \leqq 3 \,000\)， \(M \leqq 3 \,000\)．
- (\(13\) 点) \(P = (1, 1, 2, \cdots, N-1)\)．また，\(\max(B_1, B_2, \dots, B_M) < \min(A_1, A_2, \dots, A_M)\) である．
- (\(25\) 点) \(P = (1, 1, 2, \cdots, N-1)\)．
- (\(11\) 点) \(P = (N, 1, 2, \cdots, N-1)\)．
- (\(25\) 点) \(P_1 = 1\)，\(P_i < i\) (\(2 \leqq i \leqq N\))．
- (\(14\) 点) 追加の制約はない．
Examples
5 1 1 2 3 4 3 3 2 3 1 3 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\) の制約を満たす．
3 2 1 3 1 1 3
-1
どのような送り方をしても郵便局 \(1\) から郵便局 \(3\) へ荷物を運ぶことはできないため，-1 を出力する．
この入力例は小課題 \(1,2,7\) の制約を満たす．
7 1 1 2 3 4 5 6 6 4 2 5 1 5 3 6 2 7 3 7 6
5
この入力例は小課題 \(2,4,6,7\) の制約を満たす．
4 4 1 2 3 4 4 1 4 1 2 3 2 3
4
この入力例は小課題 \(2,5,7\) の制約を満たす．
7 1 1 1 3 3 4 4 5 6 1 6 3 7 1 5 1 5 1
5
この入力例は小課題 \(2,6,7\) の制約を満たす．
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
この入力例は小課題 \(2,7\) の制約を満たす．
Notes
JOI 2025 · JCIOI · CC BY-SA 4.0
Tags
No tags yet