← 返回题目列表

AtCoder · arc210_d

D. 独立设定游戏

中文机器翻译题面 查看原题

分数: 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

每个测试用例中给出的图表如下所示: