AT_ttpc2015_m.コインと無向グラフ

给定一个有 $N$ 个顶点和 $M$ 条边的无向图。图中的每个顶点 $i$（$0 \leq i < N$）上有 $C_i$ 枚硬币。所有边的长度均为 $1$。

玩家1和玩家2进行一个将硬币收集到顶点 $0$ 的游戏。玩家1和玩家2轮流重复以下操作：

1. 选择一个顶点，记为 $j$。
2. 在与顶点 $j$ 相邻的顶点中，选择一个距离顶点 $0$ 更近的顶点，记为 $k$。
3. 将顶点 $j$ 上的至少 $1$ 枚硬币移动到顶点 $k$。

（注意）不能选择顶点 $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 \leq N \leq 10^5$）和边数 $M$（$0 \leq M \leq 2 \times 10^5$）。
• 第 $2$ 行给出每个顶点 $i$（$0 \leq i < N$）上的硬币数 $C_i$（$0 \leq C_i \leq 10^8$），以空格分隔。
• 接下来的 $M$ 行，第 $3+i$ 行（$0 \leq i < M$）给出一条无向边，包含 $v_i$（$0 \leq v_i < N$）和 $w_i$（$0 \leq w_i < N$），表示在顶点 $v_i$ 和顶点 $w_i$ 之间有一条无向边。

如果玩家1获胜，输出 First。

如果玩家2获胜，输出 Second。

部分分

• 若满足 $N \leq 7$ 且 $C_0 + ... + C_{N-1} \leq 7$ 的测试点答对，可得 $50$ 分。
• 全部测试点答对，可得 $200$ 分。

共计 $250$ 分。

样例解释 1

无法将硬币向顶点 $0$ 移动，因此玩家1会输。

样例解释 2

可以将顶点 $1$ 的硬币移动到顶点 $0$，玩家1获胜。

样例解释 3

无论玩家1如何移动，玩家2都能获胜。

由 ChatGPT 4.1 翻译