题目描述

Alice 和 Bob 正在玩游戏。初始时有一个字符串可重集 $S$，Alice 和 Bob 轮流操作，Alice 先手。每次可以选择一个 $S$ 中的字符串 $s$，将其从 $S$ 中删除，并选择一个在 $s$ 中出现过的字符 $c$，将 $s$ 中的所有字符 $c$ 删除，并沿着这些删除的位置将 $s$ 划分成若干子串，将这些子串中非空的加入进集合 $S$。不能进行操作的人输。

现在给定一棵树，节点数为 $n$，每个节点上有字符。记 $\text{path}(u,v)$ 表示将节点 $u$ 到 $v$ 的最短路径所经过的节点（包括 $u$ 和 $v$）上的字符依次拼接而成的字符串。共 $q$ 次询问，每次询问给定 $u$ 和 $v$，求 $S = \{\text{path}(u,v)\}$ 时的胜者。若 Alice 获胜，同时输出第一步有多少种走法。

输入格式

从标准输入读入数据。

第一行输入两个正整数 $n$ 和 $q$。

第二行输入一个长度为 $n$ 的字符串 $s$，其第 $i$ 位 $s_i$ 表示节点 $i$ 上的字符。

接下来的 $n-1$ 行，每行两个正整数 $u$ 和 $v$，描述树上的一条边。

接下来的 $q$ 行，每行两个正整数 $u$ 和 $v$，代表一组询问。

输出格式

输出到标准输出。

输出共 $q$ 行。对于每组询问，若 Alice 获胜，输出 Alice 以及第一步的走法数，以空格分开。否则，输出 Bob。

样例

样例 1 输入

10 10
1412002124
1 2
2 3
3 4
4 5
4 6
5 7
5 8
6 9
7 10
7 6
10 2
8 8
7 2
2 9
1 7
5 1
3 8
1 2
7 1

样例 1 输出

Alice 2
Alice 1
Alice 1
Alice 1
Alice 1
Bob
Alice 1
Alice 1
Bob
Bob

子任务

保证对于所有测试点满足：$1 \le n \le 5 \times 10^4$，$1 \le q \le 10^5$，$0 \le s_i < 10$。

特殊性质 $A$：保证树的形态为一条链。

下发文件中的 $i.in/$i.ans 满足子任务 $i$ 的限制。