D - 有向グラフと数 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

N 頂点 M 辺の有向グラフがあります。このグラフの頂点 i には、整数 X_i が書かれています。ゲーム好きな兄妹がこのグラフと 1 つのチェスの駒を使ってゲームをしようとしています。

  • 最初、駒を頂点 1 に置く。
  • プレイヤーは自分のターンに、以下のいずれかちょうど 1 つの操作をしなければならない。
    • 移動 : 駒を別の頂点にちょうど 1 回移動させる。駒が頂点 i にある場合は、頂点 i から頂点 j に向かう辺があるような頂点 j にのみ移動させることができる。
    • 終了宣言 : ゲームを終了させる。
  • 交互にターンを繰り返し、どちらかのプレイヤーが終了宣言をするか、後手が 10^9 回移動をさせた直後の時点でゲームは終了となり、その時点で駒がある頂点に書かれた整数がこのゲームの スコア となる。

先手のプレイヤーがスコアを出来るだけ大きくするような行動を取り、後手のプレイヤーがスコアを出来るだけ小さくするような行動を取るとき、ゲームのスコアはいくつになるでしょうか？

入力

入力は以下の形式で標準入力から与えられる。

N M
X_1 X_2 ... X_N
A_1 B_1
A_2 B_2
:
A_M B_M
  • 1 行目には、グラフの頂点の個数を表す整数 N (1 ≦ N ≦ 100,000) と辺の個数を表す M (1 ≦ M ≦ 200,000) が空白区切りで与えられる。
  • 2 行目には、各頂点に書かれた整数を表す N 個の整数が空白区切りで与えられる。このうち i (1 ≦ i ≦ N) 番目の整数 X_i (0 ≦ X_i ≦ 10^9) は、頂点 i に書かれた整数を表す。
  • 3 行目からの M 行には、辺の情報が与えられる。このうち i (1 ≦ i ≦ M) 行目には、2 つの整数 A_i,B_i (1 ≦ A_i ≦ N, 1 ≦ B_i ≦ N, A_i \neq B_i) が空白区切りで与えられる。これは、グラフに頂点 A_i から頂点 B_i に向かう有向辺があることを表す。ただし、同じ辺が 2 回与えられることはないこと、すなわち p \neq q のとき A_p \neq A_q または B_p \neq B_q が成り立つことが保証される。

部分点

この問題には部分点が設定されている。

  • N ≦ 1000 かつ M ≦ 2000 を満たすデータセット 1 に正解した場合は、30 点が与えられる。
  • 全てのテストケースに正解した場合は、上記とは別に 70 点が与えられる。

出力

ゲームのスコアを 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

3 3
1 3 2
1 2
2 3
3 1

出力例1

2

この例では、ゲームは以下のように進行します。

  • 先手が移動を選択し、駒を頂点 1 から頂点 2 に移動させる。
  • 後手が移動を選択し、駒を頂点 2 から頂点 3 に移動させる。
  • 先手が終了宣言を選択し、ゲームを終了させる。このときスコアは 2 となる。

先手がどのような行動を取っても、後手が適切な行動を取ることによってスコアを 2 より大きくすることは出来ません。

また、後手がどのような行動を取っても、先手が適切な行動を取ることによってスコアを 2 より小さくすることは出来ません。

入力例2

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

出力例2

1

この例では、ゲームは以下のように進行します。

  • 先手が移動を選択し、駒を頂点 1 から頂点 2 に移動させる。
  • 後手が移動を選択し、駒を頂点 2 から頂点 4 に移動させる。
  • 先手が移動を選択し、駒を頂点 4 から頂点 3 に移動させる。
  • 後手が移動を選択し、駒を頂点 3 から頂点 1 に移動させる。
  • 先手が移動を選択し、駒を頂点 1 から頂点 2 に移動させる。
  • 後手が移動を選択し、駒を頂点 2 から頂点 4 に移動させる。
  • （上の流れをしばらく繰り返す）
  • 後手が 10^9 回目の移動を選択し、駒を頂点 3 から頂点 1 に移動させる。
  • この時点でゲームが終了し、スコアは 1 となる。

先手がどのような行動を取っても、後手が適切な行動を取ることによってスコアを 1 より大きくすることは出来ません。

また、後手がどのような行動を取っても、先手が適切な行動を取ることによってスコアを 1 より小さくすることは出来ません。