/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
1 から N の番号がついた N 個の頂点と、1 から M の番号がついた M 本の辺からなる無向グラフ G が与えられます。 辺 i は頂点 a_i と頂点 b_i を双方向につないでいます。
G が以下の条件の両方を満たすとき、G は よいグラフ であるといいます。はじめ、G はよいグラフであることが保証されます。
- 頂点 1 と N が非連結
- 自己ループや多重辺が存在しない
先手太郎君と後手次郎君が対戦ゲームをします。 先手太郎君と後手次郎君の手番が交互に訪れます。先手太郎君が先手です。 それぞれのプレイヤーは、手番において以下の操作が可能です。
操作：頂点 u,v を選んで u と v を双方向につなぐ辺を G に追加する。
辺を追加した結果、G がよいグラフでなくなった人の負けです。2 人が最適に行動したときに勝つのはどちらかを判定してください。
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
- 与えられるグラフはよいグラフ
- 1 つの入力ファイルにおいて、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 行目には i 番目のテストケースの勝者が先手太郎君ならば First、後手次郎君ならば 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 では先手太郎君が勝利します。以下はそのような 2 人の行動の例です。
- 先手太郎君の手番で頂点 1,2 をつなぐ辺を追加する。辺を追加したあとのグラフもよいグラフです。
- 後手次郎君はどの 2 つの頂点の間に辺を追加したとしても、グラフがよいグラフではなくなってしまいます。
- よって、勝者は先手太郎君です。
Score : 700 points
Problem Statement
Given is an undirected graph G consisting of N vertices numbered 1 through N and M edges numbered 1 through M. Edge i connects Vertex a_i and Vertex b_i bidirectionally.
G is said to be a good graph when both of the conditions below are satisfied. It is guaranteed that G is initially a good graph.
- Vertex 1 and Vertex N are not connected.
- There are no self-loops and no multi-edges.
Taro the first and Jiro the second will play a game against each other. They will alternately take turns, with Taro the first going first. In each player's turn, the player can do the following operation:
- Operation: Choose vertices u and v, then add to G an edge connecting u and v bidirectionally.
The player whose addition of an edge results in G being no longer a good graph loses. Determine the winner of the game when the two players play optimally.
You are given T test cases. Solve each of them.
Constraints
- All values in input are integers.
- 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
- The given graph is a good graph.
- In one input file, the sum of N and that of M do not exceed 2 \times 10^5.
Input
Input is given from Standard Input in the following format:
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
Each case is in the following format:
N M a_1 b_1 \vdots a_M b_M
Output
Print T lines. The i-th line should contain First if Taro the first wins in the i-th test case, and Second if Jiro the second wins in the test case.
Sample Input 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
Sample Output 1
First Second First
- In test case 1, Taro the first wins. Below is one sequence of moves that results in Taro's win:
- In Taro the first's turn, he adds an edge connecting Vertex 1 and 2, after which the graph is still good.
- Then, whichever two vertices Jiro the second would choose to connect with an edge, the graph would no longer be good.
- Thus, Taro wins.