[AGC017D] Game on Tree

# 题目描述 有一棵 $N$ 个节点的树，节点标号为 $1,2,⋯,N$，边用 $(x_i,y_i)$表示。 Alice 和 Bob 在这棵树上玩一个游戏，Alice先手，两人轮流操作： 选择一条树上存在的边，把它断开使树变成两个连通块。然后把不包含 $1$ 号点的联通块删除 当一个玩家不能操作时输，你需要算出：假如两人都按最优策略操作，谁将获胜。 # 输入格式 $N$ $x_1$ $y_1$ $x_2$ $y_2$ $...$ $x_{n-1}$ $y_{n-1}$ # 输出格式 若Alice获胜，输出```Alice``` 否则输出```Bob``` # 说明 $1 \leq N \leq 100000$ $1\leq x_i,y_i \leq N$ 保证给出的是一棵树

[problemUrl]: https://atcoder.jp/contests/agc017/tasks/agc017_d $ N $ 個の頂点 $ 1,\ 2,\ ...,\ N $ からなる木があります． この木の辺は $ (x_i,\ y_i) $ で表されます． Alice と Bob は，この木を使ってゲームをします． Alice から始め，Alice と Bob が交互に次の操作を行います． - まだ残っている辺を選び，その辺を木から取り除く．また，この操作により木は $ 2 $ つに分断されるが，そのうち頂点 $ 1 $ を含まないほうの木も取り除く． 先に操作を行えなくなったほうが負けです． $ 2 $ 人が最適に行動するとき，どちらが勝つかを求めてください．

入力は以下の形式で標準入力から与えられる。 > $ N $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ : $ x_{N-1} $ $ y_{N-1} $

Alice が勝つなら `Alice` を，Bob が勝つなら `Bob` を出力せよ．

5
1 2
2 3
2 4
4 5

Alice

5
1 2
2 3
1 4
4 5

Bob

6
1 2
2 4
5 1
6 3
3 2

Alice

7
1 2
3 7
4 6
2 3
2 4
1 5

Bob

### 制約 - $ 2\ \leq\ N\ \leq\ 100000 $ - $ 1\ \leq\ x_i,\ y_i\ \leq\ N $ - 与えられるグラフは木である． ### Sample Explanation 1 Alice が最初に頂点 $ 1,\ 2 $ を結ぶ辺を選んで操作を行うと，頂点 $ 1 $ のみを含む木になります． このとき，辺は残っていないので，Bob は操作を行うことができず，Alice が勝ちます．