AT_arc210_d.[ARC210D] Independent Set Game

给定一张简单无向图 $G$，包含 $N$ 个顶点和 $M$ 条边，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $u_i$ 与 $v_i$。

一开始，$G$ 上所有顶点都没有被染色。Alice 和 Bob 将在 $G$ 上玩一个游戏，具体规则如下：对于 $t=1,\ldots,N$：

• 如果 $t$ 是奇数，Alice 从尚未染色的顶点中选择一个，把该顶点染成黑色。
• 如果 $t$ 是偶数，Bob 从尚未染色的顶点中选择一个，把该顶点染成白色。

所有 $N$ 次操作完成后，如果所有被染成黑色的顶点构成 $G$ 的一个独立集，则 Alice 获胜；否则，Bob 获胜。当双方都采取最优策略时，请输出最后的获胜者名字。

你需要完成 $T$ 组测试，对于每组，输出胜者名字。

什么是独立集？
在一张简单无向图 $G$ 中，顶点集 $S$ 是 $G$ 的独立集，如果不存在一对通过边直接相连的顶点 $u,v$ 满足 $u\in S$ 且 $v\in S$。

输入采用如下格式：

$T$

$\mathrm{case}_1$

$\mathrm{case}_2$

$\vdots$

$\mathrm{case}_T$

每组测试输入如下：

$N$ $M$

$u_1$ $v_1$

$\vdots$

$u_M$ $v_M$

输出共 $T$ 行，第 $i$ 行为第 $i$ 组测试在双方均最优策略下胜者的名字（Alice 或 Bob）。

样例解释 1

每组样例中的图示如下：

数据范围

• $1 \leq T \leq 2 \times 10^5$
• $2 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq 2 \times 10^5$
• $1 \leq u_i < v_i \leq N$
• 给定的图是简单无向图。
• 所有测试用例中 $N$ 的总和不超过 $2 \times 10^5$。
• 所有测试用例中 $M$ 的总和不超过 $2 \times 10^5$。

由 ChatGPT 5 翻译