问题 D: Game on Tree

链接：https://ac.nowcoder.com/acm/contest/57361/D
来源：牛客网
Alice and Bob are playing a game. Initially, there is a set of string $S$. Alice and Bob take turns to play, with Alice going first. Each turn, a player can choose a string s from S, remove it from $S$, and select a character $c$ which appears in $s$. Then, they remove all occurences of character $c$ from $s$ and divide $s$ into several substrings along these removed positions. They add all non-empty substrings to the set $S$. The player who cannot make any move loses.

You are now given a tree with $n$ nodes. Each node contains a character. Let path(u,v) represent the string formed by concatenating the characters on the shortest path from node $u$ to node $v$ (including nodes $u$ and $v$). There are $q$ queries, and for each query, given nodes $u$ and $v$, you need to determine the winner when S={path(u,v)}. If Alice wins, also output the number of ways to make the first move.

The first line contains two positive integers, $n$ and $q$.
The second line contains a string of length n, where the i-th character represents the character at node $i$.
The next $n-1$ lines each contain two positive integers, $u$ and $v$, describing an edge in the tree.
Following that, there are $q$ lines, each containing two positive integers, $u$ and $v$, representing a set of queries.

Output $q$ lines in total. For each set of queries, if Alice wins, output Alice followed by the number of ways to make the first move, separated by a space. Otherwise, output Bob.

5 5
01001
2 1
3 1
4 3
5 4
4 5
4 3
1 5
2 5
5 1

Bob
Alice 1
Bob
Alice 1
Bob