M - コインと無向グラフ Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

頂点数 N で 辺の数 M の無向グラフが与えられる。 グラフの各頂点 i (0 ≦ i < N) にはコインが C_i 枚乗っている。 また、辺の長さは全て 1 とする。

プレイヤー1 と プレイヤー2 は、頂点 0 にコインを集めるゲームをする。 プレイヤー1 と プレイヤー2 は、交互に以下の手続きを繰り返す。

    1. 頂点を 1つ 選んでそれを j とする。
    1. 頂点 j に隣接する頂点のうち、頂点 j よりも 頂点 0 に距離が近い頂点を 1つ選んでそれを k とする。
    1. 頂点 j から頂点 k にコインを 1 枚以上移動させる。

（注意）頂点 0 や 頂点 0 に到達出来ない頂点を j として選択することはできない。

プレイヤー1 が先手でプレイして、コインを移動できなくなった方が負けとする。

プレイヤー1 と プレイヤー2 がともに最善を尽くす時、どちらが勝つか判定してください。

入力

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

N M
C_0 ... C_{N-1}
v_0 w_0
...
v_{M-1} w_{M-1}
  • 1 行目に頂点数を表すN(1 ≦ N ≦ 10^5)と辺の数を表すM(0 ≦ M ≦ 2*10^5)が与えられる。
  • 2 行目に頂点 i(0 ≦ i < N)にあるコインの枚数 C_i(0 ≦ C_i ≦ 10^8) が空白区切りで与えられる。
  • 3+i 行目(0 ≦ i < M)には、v_i(0 ≦ v_i < N) w_i(0 ≦ w_i < N) が空白区切りで与えられる。これは無向辺が 頂点 v_i と 頂点 w_i の間に張られていることを表す。

部分点

  • N ≦ 7 かつ C_0 + ... + C_{N-1} ≦ 7 を満たすテストケースに正解した場合、 50 点が与えられる。
  • 全てのケースに正解した場合、 200 点が与えられる。

合計 250 点

出力

プレイヤー1が勝つ場合には、 First を出力してください。

プレイヤー2が勝つ場合には、 Second を出力してください。

入力例1

2 2
1 0
0 1
1 0

出力例1

Second

頂点 0 に近づけるようにコインを動かすことが出来ないので、 プレイヤー1 が負ける。

入力例2

2 2
0 1
0 1
1 0

出力例2

First

頂点 1 のコインを頂点 0 に動かして、プレイヤー1 が勝つ。

入力例3

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

出力例3

Second

プレイヤー1 がどのように動かしても、プレイヤー2 が勝つ。

入力例4

7 0
1 1 1 1 1 1 1

出力例4

Second