{"problem":{"name":"Independent Set Game","description":{"content":"You are given a simple undirected graph $G$ with $N$ vertices and $M$ edges, where vertices are numbered $1$ to $N$. The $i$\\-th edge connects vertices $u_i$ and $v_i$. Initially, no vertices of $G$ a","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc210_d"},"statements":[{"statement_type":"Markdown","content":"You are given a simple undirected graph $G$ with $N$ vertices and $M$ edges, where vertices are numbered $1$ to $N$. The $i$\\-th edge connects vertices $u_i$ and $v_i$.\nInitially, no vertices of $G$ are colored. Alice and Bob will play a game using $G$. Alice and Bob perform the following actions in order for $t=1,\\ldots,N$:\n\n*   If $t$ is odd, Alice chooses one vertex that is not yet colored and colors that vertex black.\n*   If $t$ is even, Bob chooses one vertex that is not yet colored and colors that vertex white.\n\nAfter all $N$ actions are completed, if the set of all vertices colored black is an independent set of $G$, Alice is the winner; otherwise, Bob is the winner. Output the name of the winner when both players play optimally.\nYou are given $T$ test cases; solve each of them.\nWhat is an independent set A set $S$ consisting of vertices of a simple undirected graph $G$ is an independent set of $G$ if there does not exist a pair of vertices $u$ and $v$ connected by an edge such that $u\\in S$ and $v\\in S$.\n\n## Constraints\n\n*   $1\\leq T\\leq 2\\times 10^5$\n*   $2\\leq N\\leq 2\\times 10^5$\n*   $0\\leq M\\leq 2\\times 10^5$\n*   $1\\leq u_i < v_i \\leq N$\n*   The given graph is a simple undirected graph.\n*   The sum of $N$ over all test cases is at most $2\\times 10^5$.\n*   The sum of $M$ over all test cases is at most $2\\times 10^5$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach case is given in the following format:\n\n$N$ $M$\n$u_1$ $v_1$\n$\\vdots$\n$u_M$ $v_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc210_d","tags":[],"sample_group":[["3\n3 2\n1 2\n1 3\n4 2\n1 2\n1 3\n4 6\n1 2\n1 3\n1 4\n2 3\n2 4\n3 4","Bob\nAlice\nBob\n\nThe graph given in each test case is illustrated below:\n![image](https://img.atcoder.jp/arc210/d904a1191b2a90eea4c58343a1def228.png)"]],"created_at":"2026-03-03 11:01:14"}}