201054: [AtCoder]ARC105 E - Keep Graph Disconnected

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.