No.977 アリス仕掛けの摩天楼

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 160
作問者 : ngtkanangtkana / テスター : tempura_pptempura_pp
20 ProblemId : 3435 / 出題時の順位表
問題文最終更新日: 2020-01-31 21:28:53

問題文

喫茶店には、恋の駆け引きをする Alice と Bob の姿がありました。

王国には島が $N$ 個、橋が $N - 1$ 本あって、それぞれ 0 始まりで添字がついています。 $i$ 番目の橋は $u_i$ 番目の島と $v_i$ 番目の島を結んでいます。 これは木とは限りませんが、自己ループも多重辺もありません。

先攻は Alice さんです。Alice さんは王国を非連結にしたいです。好きな橋を1つ選んで爆破をすることができます。

後攻は Bob さんです。Bob さんは平和を願っていますから、王国を連結にしたいです。Alice さんのいたずらを見届けたあとで、間に橋の掛っていない互いに異なる島を選んで、橋を1つ掛けることが出来ます。

2 人ともの操作が終わった後で、王国が非連結になっていれば Alice さんの勝ちです。連結になっていれば Bob さんの勝ちです。勝つのが Alice さんならば、'Alice' と、Bob さんならば 'Bob' と一行で出力してください。

(21:27 Alice さんが破壊できる橋、Bob さんが建設できる橋が1本ずつであることを追記。)

制約

入力は全部で $N$ 行となり、以下の制約を満たします。

  • $2 \leq N \leq 10^5$
  • $0 \leq u_i, v_i < N \ (0 \leq i < N - 1)$
  • $u_i \neq v_i \ ( 0 \leq i < N - 1)$
  • $\{u_i, v_i\} \neq \{u_j, v_j\} \ ( i \neq j) $

入力

$N$
$u_0\ v_0$
$\dots$
$u_{N - 2}\ v_{N - 2}$

1 行目に島の数 $N$ が与えられます。
続く $N - 1$ 行には、橋の情報が入力されます。橋 $i (i = 0, \dots , N - 1)$ は 島 $u_i$ と島 $v_i$ を結びます。

出力

一行で "Alice" または "Bob" を入力してください。
最後に改行してください。

サンプル

サンプル1
入力
3
0 1
1 2
出力
Bob

Alice さんがどの橋を爆破しても、Bob さんは再びゆきこ市を連結にすることができます。

サンプル2
入力
7
0 1
0 2
0 3
1 2
1 3
2 3
出力
Alice

例えば Alice さんが島 $0$ と島 $1$ を結ぶ橋を爆破したとき、Bob さんは再びゆきこ市を連結にすることができません。孤立していますが、島 $4, 5, 6$ が存在することに注意してください。

サンプル3
入力
7
0 1
1 2
2 3
2 4
3 4
4 5
出力
Alice

Boooo! Alice の勝ち!
何で負けたか、明日まで考えといてください。
そしたら何かが見えてくるはずです。
ほな、爆破します。

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。