[ARC105E] Keep Graph Disconnected
题意翻译
### 题意
有一张 $n$ 个点 $m$ 条边的无向图,两个人轮流操作,向图中加一条边,每次操作后需要满足下面两个条件:
1. 节点 $1$ 和节点 $n$ 不连通。
2. 没有重边和自环。
谁不能操作就输了,问谁能赢。
题目描述
[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
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\ \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 $ つの頂点の間に辺を追加したとしても、グラフがよいグラフではなくなってしまいます。 - よって、勝者は先手太郎君です。