AT_arc038_d [ARC038D] 有向グラフと数

[problemUrl]: https://atcoder.jp/contests/arc038/tasks/arc038_d $ 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 $ が成り立つことが保証される。

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

### 部分点 この問題には部分点が設定されている。 - $ N\ ≦\ 1000 $ かつ $ M\ ≦\ 2000 $ を満たすデータセット $ 1 $ に正解した場合は、$ 30 $ 点が与えられる。 - 全てのテストケースに正解した場合は、上記とは別に $ 70 $ 点が与えられる。 ### Sample Explanation 1 この例では、ゲームは以下のように進行します。 - 先手が移動を選択し、駒を頂点 $ 1 $ から頂点 $ 2 $ に移動させる。 - 後手が移動を選択し、駒を頂点 $ 2 $ から頂点 $ 3 $ に移動させる。 - 先手が終了宣言を選択し、ゲームを終了させる。このときスコアは $ 2 $ となる。 先手がどのような行動を取っても、後手が適切な行動を取ることによってスコアを $ 2 $ より大きくすることは出来ません。 また、後手がどのような行動を取っても、先手が適切な行動を取ることによってスコアを $ 2 $ より小さくすることは出来ません。 ### Sample Explanation 2 この例では、ゲームは以下のように進行します。 - 先手が移動を選択し、駒を頂点 $ 1 $ から頂点 $ 2 $ に移動させる。 - 後手が移動を選択し、駒を頂点 $ 2 $ から頂点 $ 4 $ に移動させる。 - 先手が移動を選択し、駒を頂点 $ 4 $ から頂点 $ 3 $ に移動させる。 - 後手が移動を選択し、駒を頂点 $ 3 $ から頂点 $ 1 $ に移動させる。 - 先手が移動を選択し、駒を頂点 $ 1 $ から頂点 $ 2 $ に移動させる。 - 後手が移動を選択し、駒を頂点 $ 2 $ から頂点 $ 4 $ に移動させる。 - （上の流れをしばらく繰り返す） - 後手が $ 10^9 $ 回目の移動を選択し、駒を頂点 $ 3 $ から頂点 $ 1 $ に移動させる。 - この時点でゲームが終了し、スコアは $ 1 $ となる。 先手がどのような行動を取っても、後手が適切な行動を取ることによってスコアを $ 1 $ より大きくすることは出来ません。 また、後手がどのような行動を取っても、先手が適切な行動を取ることによってスコアを $ 1 $ より小さくすることは出来ません。