树上游戏

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

题目描述

Alice和Bob最近又在寻找一些好玩的游戏，直到有一天他们发现了一颗有根树。

树的根节点为 $1$ ，树上每个点有 $3$ 种类型，分别对应 $1，2，3$ 。

类型 $1 ,2$ 分别表示向上跳 $1$ 格，跳 $2$ 格。类型 $3$ 表示向上跳 $1$ 格或 $2$ 格。

Alice提议她随便选一个叶子节点（不包括根节点）开始向上跳，谁先不能跳谁就输。

Bob觉得非常的不公平，所以他试图破坏这个树，来获得胜利。

Bob能破坏有根树的一条边，从而使得跳跃无法越过该边。

Alice，Bob想要知道破坏第 $i$ 条边后谁能获得胜利，两人都按照最优策略进行游戏。

注：此处破坏第 $i$ 条边并不会改变树的形态，并且每次破坏操作独立。

输入共 $n+1$ 行。

第一行一个整数表示 $n\ (2≤n≤10^5)$ 。

第二行 $n$ 个整数 $a_i\ (1≤a_i≤3)$ 表示节点类型。

接下来 $n-1$ 行，表示第 $i$ 条边 $u_i,v_i \ (1≤u_i,v_i≤n)$ 。

输出共 $n−1$ 行，分别表示第 $i$ 条边被破坏后，该游戏谁能获得胜利。

如果Alice赢则输出"Alice",否则输出"Bob"（不包括双引号）。

示例1

复制

复制

Alice
Bob

若破坏1-2这条边，Alice选择3号节点作为起点，向上跳一步，Bob无法再跳，Alice赢。

若破坏1-3这条边，Alice无论选择2，3哪一个节点作为起点，都无法再跳，Bob赢。

示例2

复制

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

复制

Alice
Bob
Bob
Alice
Bob
Bob
Bob