分数: 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 选择哪两个顶点与一条边连接,该图都将不再是好的。
- 因此,太郎获胜。