二叉树游戏

题号：NC236262
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Alice和Bob在玩二叉树游戏，游戏规则如下：给一个 $n$ 个节点的二叉树，根节点是1，两人轮流操作。每次操作可以取走一棵完全二叉子树，当一名玩家不能操作时则视为失败，Alice先手。如果两个人都以最优策略来进行游戏，请问最终谁能获胜

对于一棵二叉树，如果它的所有非叶子节点都有两个子结点，并且所有叶子节点的深度相同，那么这棵二叉树是完全二叉树。显然，如果一棵树只有一个节点，那么它也是完全二叉树。

第一行输入一个整数 $n(1\le n \le 5\times 10^5)$ ，表示二叉树的结点个数。

接下来 $n-1$ 行，每一行输入两个整数 $u_i,v_i(1\le u_i,v_i \le n)$ ，表示节点 $u_i,v_i$ 之间有一条连边。保证输入是一棵二叉树。

输出一行，如果Alice必胜，则输出"Alice"；如果Bob必胜，则输出"Bob"。

示例1

复制

3
1 2
2 3

复制

Alice

示例2

复制

复制

Bob