#arc105e. [arc105_e]Keep Graph Disconnected
[arc105_e]Keep Graph Disconnected
题目描述
给定一个由 个顶点编号为 到 和 条边编号为 到 的无向图 。边 双向连接了顶点 和顶点 。
当满足以下两个条件时, 被称为 良好图 。保证 最初是一个良好图。
- 顶点 和顶点 没有连接。
- 没有自环和多重边。
太郎是第一名玩家,次郎是第二名玩家,他们将相互对战。他们轮流进行游戏,太郎先行。在每个玩家的回合中,玩家可以执行以下操作:
- 操作:选择顶点 和 ,然后双向添加一条连接 和 的边到 中。
当添加边使得 不再是良好图时,进行该操作的玩家失败。确定当两个玩家都以最佳方式进行游戏时的胜者。
给定 个测试用例,请解决每个测试用例。
约束条件
- 输入中的所有值都是整数。
- 给定的图是一个良好图。
- 在一个输入文件中, 和 的总和不超过 。
输入
输入从标准输入中给出,格式如下:
每个测试用例的格式如下:
输出
打印 行。第 行应包含以下内容:
如果太郎是在第 个测试用例中获胜的,则输出 First
;如果次郎是在第 个测试用例中获胜的,则输出 Second
。
示例输入1
示例输出1
- 在测试用例 1 中,太郎是获胜者。以下是一种使太郎获胜的移动序列:
- 在太郎的回合中,他添加了一条连接顶点 和 的边,此时图仍然是良好图。
- 然后,无论次郎选择哪两个顶点添加一条边连接,图都不再是良好图。
- 因此,太郎获胜。