← 返回题目列表

AtCoder · ttpc2015_m

M. 硬币和无向图

中文机器翻译题面 查看原题

問題文

頂点数 N 含边数 给出了 M 的无向图。 图的每个顶点 i (0 ≦ i < N)有硬币。 C_i 已在船上。 另外,所有边的长度都是 1 。

玩家 1 和玩家 2 是顶点 0 玩一个收集硬币的游戏。 玩家 1 和玩家 2 轮流重复以下过程。

    1. 选择一个顶点并选择它 在与 j 。
    1. 頂点 j 相邻的顶点中,顶点 顶点比 j 选择靠近 0 的一个顶点并选择它 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 获胜, 玩家 1 输了,因为他无法将硬币移近 Second 。


入力例1

2 2
1 0
0 1
1 0

出力例1

Second

頂点 0 。


入力例2

2 2
0 1
0 1
1 0

出力例2

First

頂点 1 硬币到顶部 玩家 1 通过移动 0 获胜。


入力例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