题目描述
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$。
| 子任务编号 | $n \le$ | $q \le$ | $s_i \le$ | 特殊性质 | 分数 |
|---|---|---|---|---|---|
| $1$ | $10$ | $10^3$ | $10$ | 无 | $7$ |
| $2$ | $500$ | $2 \times 10^4$ | $10$ | $A$ | $13$ |
| $3$ | $3,000$ | $2 \times 10^4$ | $10$ | $A$ | $12$ |
| $4$ | $5 \times 10^4$ | $10^5$ | $10$ | $A$ | $19$ |
| $5$ | $2 \times 10^4$ | $2 \times 10^4$ | $5$ | 无 | $24$ |
| $6$ | $5 \times 10^4$ | $10^5$ | $10$ | 无 | $25$ |
特殊性质 $A$：保证树的形态为一条链。
下发文件中的 $i.in/$i.ans 满足子任务 $i$ 的限制。