{"problem":{"name":"Keep Graph Disconnected","description":{"content":"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 sai","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc105_e"},"statements":[{"statement_type":"Markdown","content":"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.\n$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.\n\n*   Vertex $1$ and Vertex $N$ are not connected.\n*   There are no self-loops and no multi-edges.\n\nTaro 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:\n\n*   Operation: Choose vertices $u$ and $v$, then add to $G$ an edge connecting $u$ and $v$ bidirectionally.\n\nThe 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.\nYou are given $T$ test cases. Solve each of them.\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 \\leq T \\leq 10^5$\n*   $2 \\leq N \\leq 10^{5}$\n*   $0 \\leq M \\leq \\min(N(N-1)/2,10^{5})$\n*   $1 \\leq a_i,b_i \\leq N$\n*   The given graph is a good graph.\n*   In one input file, the sum of $N$ and that of $M$ do not exceed $2 \\times 10^5$.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach case is in the following format:\n\n$N$ $M$\n$a_1$ $b_1$\n$\\vdots$\n$a_M$ $b_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc105_e","tags":[],"sample_group":[["3\n3 0\n6 2\n1 2\n2 3\n15 10\n12 14\n8 3\n10 1\n14 6\n12 6\n1 9\n13 1\n2 5\n3 9\n7 2","First\nSecond\nFirst\n\n*   In test case $1$, Taro the first wins. Below is one sequence of moves that results in Taro's win:\n    *   In Taro the first's turn, he adds an edge connecting Vertex $1$ and $2$, after which the graph is still good.\n    *   Then, whichever two vertices Jiro the second would choose to connect with an edge, the graph would no longer be good.\n    *   Thus, Taro wins."]],"created_at":"2026-03-03 11:01:14"}}