I. Palindrome tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree consisting of $$$n$$$ vertices. Each vertex contains some symbol $$$c_i$$$. You need to remove a certain number of vertices so that the remaining set of vertices is connected and it is impossible to find a palindromic path of length greater than $$$k$$$. A simple path is called palindromic if writing out the characters written at the vertices in forward and reverse order results in the same string.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ — the number of vertices in the tree and the maximum length of a palindromic path.

The second line contains a string $$$s$$$ consisting only of lowercase English letters of length $$$n$$$, where the $$$i$$$-th character $$$c_i$$$ corresponds to the character written at the $$$i$$$-th vertex.

The next $$$(n - 1)$$$ lines contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$x_i \ne y_i$$$, $$$1 \le x_i, y_i \le n$$$) — numbers of vertices connected by an edge.

$$$$$$ 1 \le k \le n \le 2\,000 $$$$$$

Output

In the first line print the number $$$m$$$ — the number of vertices remaining after the removal.

In the second line print $$$m$$$ integers $$$b_i$$$ — the numbers of the remaining vertices.

If there is more than one answer, then print the minimum answer that is not a prefix of another answer.

The answer $$$a$$$ is less than $$$b$$$ if and only if there exists $$$p$$$ such that $$$a_p \lt b_p$$$ and $$$a_j = b_j$$$ for $$$1 \le j \lt p$$$.

The answer $$$a$$$ is a prefix of $$$b$$$ if and only if $$$|a| \lt |b|$$$ and $$$a_j = b_j$$$ for $$$1 \le j \le |a|$$$, where $$$|a|$$$  is the length of the array $$$a$$$.

Examples
Input
3 2
aba
1 2
1 3
Output
3
1 2 3
Input
3 2
aba
1 2
2 3
Output
2
1 2
Note

In the second example, several answers are suitable: $$$(1, 2)$$$, $$$(2, 1)$$$, $$$(2, 3)$$$, $$$(3, 2)$$$, $$$(1)$$$, $$$(2)$$$ , $$$(3)$$$. The answers $$$(1)$$$, $$$(2)$$$, $$$(3)$$$ are the prefixes of the answers $$$(1, 2)$$$, $$$(2, 1)$$$ and $$$(3, 2)$$$ respectively. Among the remaining suitable answers, the minimum is $$$(1, 2)$$$.