分数: 800 点
问题陈述
给你一个简单的无向图 G 与 N 顶点和 M 边,其中顶点已编号 1 to N。的 i第一条边连接顶点 u_i 和 v_i.
最初,没有顶点 G 是彩色的。爱丽丝和鲍勃将玩一个游戏 G。 Alice 和 Bob 执行以下操作以便 t=1,\ldots,N:
- If t 很奇怪,Alice 选择一个尚未着色的顶点并将该顶点着色为黑色。
- If t 是偶数,Bob 选择一个尚未着色的顶点并将该顶点着色为白色。
毕竟 如果所有黑色顶点的集合是独立的集合,则 N 操作已完成 G,Alice 获胜;否则,鲍勃就是赢家。当双方都发挥最佳时,输出获胜者的名字。
你被给予 T 测试用例;解决它们中的每一个。
什么是独立集
一套 S 由简单无向图的顶点组成 G 是一组独立的 G 如果不存在一对顶点 u 和 v 由边连接,使得 u\in S 和 v\in S.约束
- 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.
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个案例均按以下格式给出:
N M u_1 v_1 \vdots u_M v_M
输出
输出 T 行。的 i- 第行应包含获胜者的姓名(Alice or Bob) 为 i- 当两个玩家都发挥最佳状态时的第一个测试用例。
示例输入 1
3 3 2 1 2 1 3 4 2 1 2 1 3 4 6 1 2 1 3 1 4 2 3 2 4 3 4
示例输出 1
Bob Alice Bob
每个测试用例中给出的图表如下所示:
