← 返回题目列表

AtCoder · arc105_e

E. 保持图表断开连接

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

分数: 700 点

问题陈述

给定的是一个无向图 G 组成 N 顶点编号 1 通过 N 和 M 边编号 1 通过 M。 边缘 i 连接顶点 a_i 和顶点 b_i 双向。

G 据说是 好图 当满足以下两个条件时。可以保证 G 最初是一个很好的图表。

  • 顶点 1 和顶点 N 未连接。
  • 没有自环,也没有多边边。

第一太郎和第二二郎将进行一场比赛。 他们轮流轮流,太郎先走。 在每个玩家的回合中,玩家可以进行以下操作:

  • 操作:选择顶点 u 和 v,然后添加到 G 边缘连接 u 和 v 双向。

玩家的加边导致 G 不再是一个好的图表了。当两名玩家发挥最佳时确定游戏的胜利者。

你被给予 T 测试用例。解决它们中的每一个。

约束

  • 输入中的所有值都是整数。
  • 1 \leq T \leq 10^5
  • 2 \leq N \leq 10^{5}
  • 0 \leq M \leq \min(N(N-1)/2,10^{5})
  • 1 \leq a_i,b_i \leq N
  • 给定的图是一个很好的图。
  • 在一个输入文件中, N 以及 M 不超过 2 \times 10^5.

输入

输入由标准输入按以下格式给出:

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

每个案例的格式如下:

N M
a_1 b_1
\vdots
a_M b_M

输出

打印 T 行。的 i- 第行应包含 First 如果太郎第一个获胜 i- 第一个测试用例,以及 Second 如果第二个 Jiro 在测试用例中获胜。


示例输入 1

3
3 0
6 2
1 2
2 3
15 10
12 14
8 3
10 1
14 6
12 6
1 9
13 1
2 5
3 9
7 2

示例输出 1

First
Second
First
  • 在测试用例中 1,太郎先胜。以下是导致太郎获胜的一系列动作:
    • 在太郎第一个回合中,他添加了一条连接顶点的边 1 和 2,之后图表仍然很好。
    • 然后,无论第二个 Jiro 选择哪两个顶点与一条边连接,该图都将不再是好的。
    • 因此,太郎获胜。