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 翻译