AT_arc105_e.[ARC105E] Keep Graph Disconnected

给定一个包含 $N$ 个编号为 $1$ 到 $N$ 的顶点和 $M$ 条编号为 $1$ 到 $M$ 的边的无向图 $G$。第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$，是双向的。

当 $G$ 同时满足以下两个条件时，称 $G$ 为“好图”。初始时，保证 $G$ 是好图。

• 顶点 $1$ 和顶点 $N$ 不连通。
• 不存在自环或重边。

先手太郎君和后手次郎君进行对抗游戏。两人轮流操作，太郎君先手。每一回合，当前玩家可以进行如下操作：

操作：选择两个顶点 $u,v$，在 $G$ 中添加一条连接 $u$ 和 $v$ 的双向边。

如果添加边后，$G$ 不再是好图，则当前玩家输掉游戏。请判断在两人都采取最优策略的情况下，谁会获胜。

给定 $T$ 组测试数据，请分别输出每组的胜者。

输入以如下格式从标准输入给出。

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

每组测试数据格式如下：

$N$ $M$
$a_1$ $b_1$
$\vdots$
$a_M$ $b_M$

输出 $T$ 行。第 $i$ 行输出第 $i$ 个测试用例的胜者。如果先手太郎君获胜，输出 First；如果后手次郎君获胜，输出 Second。

限制条件

• 所有输入均为整数。
• $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$。

样例解释 1

• 在测试用例 $1$ 中，先手太郎君获胜。以下是两人行动的一个例子：
  • 先手太郎君在顶点 $1$ 和 $2$ 之间添加一条边。添加后图仍为好图。
  • 后手次郎君无论在任意两个顶点之间添加边，都会导致图不再是好图。
  • 因此，胜者为先手太郎君。

由 ChatGPT 4.1 翻译