I. Mortal Kombat
time limit per test
3.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Khaled and his brother are having an intense Mortal Kombat match. Determined to secure a "Flawless Victory" and leave his brother no room to breathe, Khaled decides to unleash a relentless chain of special moves.

In this game, the combo system is represented as a rooted tree consisting of $$$n$$$ nodes, where node $$$1$$$ is the root. Each node $$$i$$$ has a specific button assigned to it, represented by a lowercase English letter $$$c_i$$$.

To execute the special move associated with node $$$x$$$, a player must input the exact sequence of buttons along the simple path from the root to node $$$x$$$. Let this string of button presses be $$$S_x$$$.

For his ultimate attack, Khaled wants to execute two special moves, $$$u$$$ and $$$v$$$, in a single rapid string of inputs. A sequence of button presses is considered valid if both $$$S_u$$$ and $$$S_v$$$ are contiguous substrings$$$^\dagger$$$ of this sequence(they can overlap).

Since Khaled wants to execute the attack as quickly as possible, he needs your help to determine the minimum number of button presses required to perform both moves. You are given $$$q$$$ queries, each consisting of two nodes $$$u$$$ and $$$v$$$.For each query, output the minimum length of a valid button sequence.

————————————————————————

$$$^\dagger$$$A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 5 * 10 ^ 5$$$) — the number of nodes in the combo tree and the number of queries, respectively.

The second line contains a string $$$C$$$ of length $$$n$$$ consisting of lowercase English letters, where the $$$i$$$ - th character represents $$$c_i$$$, the button assigned to node $$$i$$$.

Each of the next $$$n - 1$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le n$$$), denoting an edge between node $$$x$$$ and node $$$y$$$ in the tree.

Each of the next $$$q$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u \neq v \le n$$$) — the nodes representing the two special moves Khaled wants to execute.

Output

For each query, print a single integer on a new line— the minimum number of button presses required to execute both special moves $$$u$$$ and $$$v$$$.

Example
Input
5 2
abaab
1 2
2 3
1 4
4 5
3 5
2 4
Output
4
3
Note

The string of node 3 is $$$S_3 = $$$ "aba" (path $$$1 \to 2 \to 3$$$).

The string of node 5 is $$$S_5 = $$$ "aab" (path $$$1 \to 4 \to 5$$$).

The string of node 2 is $$$S_2 = $$$ "ab" (path $$$1 \to 2$$$).

The string of node 4 is $$$S_4 = $$$ "aa" (path $$$1 \to 4$$$).

For the first query($$$u = 3$$$, $$$v = 5$$$) : Khaled needs the strings "aba" and "aab". The shortest sequence that contains both is "aaba" (length 4).

For the second query($$$u = 2$$$, $$$v = 4$$$) : Khaled needs the strings "ab" and "aa". The shortest sequence that contains both is "aab"(length 3).