这是问题的困难版本。在此版本中,不保证 $$$u = v$$$。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
Alice 和 Bob 正在树上玩一个有趣的游戏。该游戏在具有 $$$n$$$ 个顶点的树上进行,编号从 $$$1$$$ 到 $$$n$$$。回想一下,具有 $$$n$$$ 顶点的树是具有 $$$n - 1$$$ 边的无向连通图。
Alice 和 Bob 轮流,Alice 先走。每个玩家都从某个顶点开始。
在他们的回合中,玩家必须从当前顶点移动到尚未被任何人访问过的相邻顶点。第一个无法采取行动的玩家失败。
给定两个顶点 $$$u$$$ 和 $$$v$$$。将顶点 $$$u$$$ 到 $$$v$$$ 的简单路径表示为数组 $$$p_1, p_2, p_3, \ldots, p_m$$$,其中 $$$p_1 = u$$$, $$$p_m = v$$$,并且对于所有 $$$i$$$,$$$p_i$$$ 和 $$$p_{i + 1}$$$ 之间有一条边($$$1 \le i < m$$$)。
对于每个 $$$j$$$(其中 $$$1 \le j \le m$$$),如果 Alice 从顶点 $$$1$$$ 开始,Bob 从顶点 $$$p_j$$$ 开始,则需要确定游戏的获胜者。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 树中的顶点数。
以下 $$$n - 1$$$ 行中的每一行都包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \le a, b \le n$$$),表示顶点 $$$a$$$ 和 $$$b$$$ 之间的无向边。保证这些边形成一棵树。
每个测试用例的最后一行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$2 \le u, v \le n$$$)。
保证从$$$u$$$到$$$v$$$的路径不经过顶点$$$1$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出 $$$m$$$ 行。
在第 $$$i$$$ 行中,如果 Alice 从顶点 $$$1$$$ 开始并且 Bob 从顶点 $$$p_i$$$ 开始,则打印游戏的获胜者。如果 Alice 获胜,则打印“Alice”(不带引号),否则打印“Bob”(不带引号)。
示例
输入 #1
3 3 1 2 2 3 2 3 6 1 2 1 3 2 4 2 5 1 6 4 5 4 1 2 1 3 2 4 2 4
输出 #1
Bob Alice Alice Bob Alice Bob Alice
注意
第一个示例中的树。
在第一个测试用例中,路径将为 ($$$2,3$$$)。如果鲍勃从顶点 $$$2$$$ 开始,爱丽丝将无法在第一回合移动到任何地方,并且会失败。
但是,如果 Bob 从顶点 $$$3$$$ 开始,Alice 将移动到顶点 $$$2$$$,而 Bob 将没有剩余的顶点可供访问,并且会失败。