配点 : $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 を出力せよ。

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

First
Second
First

• テストケース $1$ では先手太郎君が勝利します。以下はそのような $2$ 人の行動の例です。- 先手太郎君の手番で頂点 $1,2$ をつなぐ辺を追加する。辺を追加したあとのグラフもよいグラフです。
  • 後手次郎君はどの $2$ つの頂点の間に辺を追加したとしても、グラフがよいグラフではなくなってしまいます。
  • よって、勝者は先手太郎君です。
• 先手太郎君の手番で頂点 $1,2$ をつなぐ辺を追加する。辺を追加したあとのグラフもよいグラフです。
• 後手次郎君はどの $2$ つの頂点の間に辺を追加したとしても、グラフがよいグラフではなくなってしまいます。
• よって、勝者は先手太郎君です。