AT_arc105_e [ARC105E] Keep Graph Disconnected

[problemUrl]: https://atcoder.jp/contests/arc105/tasks/arc105_e $ 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 $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ - 与えられるグラフはよいグラフ - $ 1 $ つの入力ファイルにおいて、$ N $ の総和、$ M $ の総和はどちらも $ 2\ \times\ 10^5 $ を超えない。 ### Sample Explanation 1 \- テストケース $ 1 $ では先手太郎君が勝利します。以下はそのような $ 2 $ 人の行動の例です。 - 先手太郎君の手番で頂点 $ 1,2 $ をつなぐ辺を追加する。辺を追加したあとのグラフもよいグラフです。 - 後手次郎君はどの $ 2 $ つの頂点の間に辺を追加したとしても、グラフがよいグラフではなくなってしまいます。 - よって、勝者は先手太郎君です。