题目描述

给定一棵有 $N$ 个顶点的有根树，顶点编号为 $1$ 到 $N$。顶点 $1$ 是根，对于每个 $i\ (2\leq i \leq N)$，顶点 $i$ 的父节点为 $P_i$。

树上的部分顶点上写有 $0$ 到 $N$ 之间的整数。这些信息由数列 $A=(A_1,A_2,\ldots,A_N)$ 给出，若 $A_i\neq -1$，则表示顶点 $i$ 上写有整数 $A_i$；若 $A_i=-1$，则表示顶点 $i$ 上没有写整数。

Alice 和 Bob 进行游戏。Alice 先手，双方轮流操作，直到所有顶点都被写上整数。每次操作可以选择一个尚未写整数的顶点，并在其上写一个 $0$ 到 $N$ 之间的整数。

操作结束后，对于每个顶点 $v$，定义 $f(v)$ 为“在顶点 $v$ 的子树中（包括 $v$ 本身），没有被写下的最小非负整数”。

若存在某个顶点 $v$ 满足 $f(v)=K$，则 Alice 获胜，否则 Bob 获胜。请判断在双方都采取最优策略的情况下，谁会获胜。

有 $T$ 组测试数据，请分别作答。

输入格式

输入按以下格式从标准输入读入。

$T$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_T$

每组数据格式如下：

$N\ K$
$P_2\ P_3\ \ldots\ P_N$
$A_1\ A_2\ \ldots\ A_N$

输出格式

输出 $T$ 行。对于第 $i$ 组测试数据，若 Alice 获胜则输出 Alice，否则输出 Bob。

样例 1

输入

2
4 2
1 1 2
-1 -1 3 1
6 4
1 2 2 1 3
-1 -1 -1 -1 -1 -1

输出

Alice
Bob

说明/提示

限制

• $1\leq T\leq 10^3$
• $2\leq N\leq 10^3$
• $0\leq K\leq N$
• $1\leq P_i < i\ (2\leq i\leq N)$
• $-1\leq A_i\leq N\ (1\leq i\leq N)$
• 所有输入的数均为整数
• 所有测试数据中 $N$ 的总和不超过 $2\times 10^3$

样例解释 1

对于第 $1$ 组测试数据，Alice 可以在顶点 $2$ 上写 $0$，无论 Bob 如何操作，都有 $f(2)=2$，因此 Alice 获胜。对于第 $2$ 组测试数据，Bob 可以通过合理选择写入的整数，使得不存在 $f(v)=4$ 的顶点，因此 Bob 获胜。

由 ChatGPT 4.1 翻译