D - Independent Set Game Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 800 点

問題文

頂点に 1 から N の番号が付いた N 頂点 M 辺の単純無向グラフ G が与えられます．i 番目の辺は頂点 u_i と頂点 v_i を結んでいます．

G の頂点にははじめ色が塗られていません．Alice と Bob が G を使ってゲームをします．Alice と Bob は t=1,\ldots,N の順に次の行動を行います．

  • t が奇数ならば，Alice がまだ色の塗られていない頂点をひとつ選び，その頂点を黒色で塗る．
  • t が偶数ならば，Bob がまだ色の塗られていない頂点をひとつ選び，その頂点を白色で塗る．

N 回すべての行動が終わった時点で，黒色で塗られた頂点全体が G の独立集合であれば Alice が勝者，そうでなければ Bob が勝者となります．両者が最適に行動した場合の勝者の名前を出力してください．

T 個のテストケースが与えられるので，それぞれについて解いてください．

独立集合とは 単純無向グラフ G の頂点からなる集合 S が G の独立集合であるとは，辺で結ばれた 2 頂点 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 行目には i 番目のテストケースについて，両者が最適に行動した場合の勝者の名前（Alice または Bob）を出力してください．

入力例 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

各テストケースで与えられるグラフを図示すると次のようになります．

Score : 800 points

Problem Statement

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

  • If t is odd, Alice chooses one vertex that is not yet colored and colors that vertex black.
  • If t is even, Bob chooses one vertex that is not yet colored and colors that vertex white.

After 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.

You are given T test cases; solve each of them.

What 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.

Constraints

  • 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
  • The given graph is a simple undirected graph.
  • The sum of N over all test cases is at most 2\times 10^5.
  • The sum of M over all test cases is at most 2\times 10^5.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each case is given in the following format:

N M
u_1 v_1
\vdots
u_M v_M

Output

Output T lines. The i-th line should contain the name of the winner (Alice or Bob) for the i-th test case when both players play optimally.

Sample Input 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

Sample Output 1

Bob
Alice
Bob

The graph given in each test case is illustrated below: