描述

Alice和Bob的父母是某零件工厂的工人。这个工厂是由n个节点,n-1条有向边构成的树形图,其中1号节点为根节点。每一个节点要么是一个仓库,要么是一个加工机器,其中1号节点为仓库。每一个机器有且仅有一条指向其他节点的有向传送带。每条传送带有一个传输速率上限,为了避免堵塞,一个节点的输出传送带的传输速率上限一定大于等于该节点输入速率上限(也就是指向它的所有节点的输出速率上限之和)(1号节点除外,也就是说除1号节点外的仓库和机器都满足这个性质)。如果一个节点的输出速率上限为0,那么该节点为一个仓库,即该点不能向外运输零件。

某个星期天,工厂中没有工人,Alice和Bob偷偷溜进工厂里玩。每一个节点上都残留着一些零件,他们决定用这些零件玩一个游戏。他们将轮流进行操作,Alice先手。每个人的一回合,Alice或Bob可以操作一个节点的机器,将某一个节点中不超过传送最大输出速率(但不为0)的零件沿着传送带送到下一个节点。不能操作的人判负。

现在给出整个工厂的结构,每个节点内残留的零件个数,求问谁有必胜策略。

输入格式

第一行一个正整数T,表示测试数据组数。

接下来为T组数据:

每组数据的第一行有1个正整数n,表示工厂的节点数。

接下来由n-1行,第i行(即该组数据i+1行)由3个整数fa(1≤fa≤n),num(num≥0),extra(extra≥0),分别表示第i+1号节点的输出传送带指向fa号节点,第i+1号节点上残留的零件数为num,第i+1号节点的输出传送带的输出速率上限为该节点的输入速率上限加上extra。(由于1号仓库没有输出传送带,并且之中残留的零件数对游戏没有影响,所以输入是从2号节点开始的。)

输出格式

对于每组测试数据数据,输出一行“Alice”或“Bob”,表示有必胜策略者的名字。

样例输入

5
5
1 5 0
1 1 0
2 6 1
3 4 1
5
1 3 1
1 1 1
3 6 2
4 6 0
5
1 0 1
2 4 1
2 4 0
3 3 2
5
1 6 1
2 4 1
3 5 2
2 4 2
5
1 5 0
2 6 1
1 4 0
2 5 0

样例输出

Bob
Bob
Bob
Alice
Alice

数据范围与约定

来源

原创