#arc105e. [arc105_e]Keep Graph Disconnected

[arc105_e]Keep Graph Disconnected

题目描述

给定一个由 NN 个顶点编号为 11NNMM 条边编号为 11MM 的无向图 GG。边 ii 双向连接了顶点 aia_i 和顶点 bib_i

当满足以下两个条件时,GG 被称为 良好图 。保证 GG 最初是一个良好图。

  • 顶点 11 和顶点 NN 没有连接。
  • 没有自环和多重边。

太郎是第一名玩家,次郎是第二名玩家,他们将相互对战。他们轮流进行游戏,太郎先行。在每个玩家的回合中,玩家可以执行以下操作:

  • 操作:选择顶点 uuvv,然后双向添加一条连接 uuvv 的边到 GG 中。

当添加边使得 GG 不再是良好图时,进行该操作的玩家失败。确定当两个玩家都以最佳方式进行游戏时的胜者。

给定 TT 个测试用例,请解决每个测试用例。

约束条件

  • 输入中的所有值都是整数。
  • 1T1051 \leq T \leq 10^5
  • 2N1052 \leq N \leq 10^{5}
  • 0Mmin(N(N1)/2,105)0 \leq M \leq \min(N(N-1)/2,10^{5})
  • 1ai,biN1 \leq a_i,b_i \leq N
  • 给定的图是一个良好图。
  • 在一个输入文件中,NNMM 的总和不超过 2×1052 \times 10^5

输入

输入从标准输入中给出,格式如下:

TT case1\mathrm{case}_1 \vdots caseT\mathrm{case}_T

每个测试用例的格式如下:

NN MM a1a_1 b1b_1 \vdots aMa_M bMb_M

输出

打印 TT 行。第 ii 行应包含以下内容:

如果太郎是在第 ii 个测试用例中获胜的,则输出 First;如果次郎是在第 ii 个测试用例中获胜的,则输出 Second

示例输入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 中,太郎是获胜者。以下是一种使太郎获胜的移动序列:
    • 在太郎的回合中,他添加了一条连接顶点 1122 的边,此时图仍然是良好图。
    • 然后,无论次郎选择哪两个顶点添加一条边连接,图都不再是良好图。
    • 因此,太郎获胜。