Minimum Coloring on Tree Paths

You are given an unrooted tree with \( m \) nodes. You are allowed to choose any node with degree greater than \( 1 \) as the root. Then, you may color some nodes (the root, internal nodes, or leaves) in either black or white. Your coloring scheme must guarantee that on the simple path from the root to each leaf there is at least one colored node (the leaf itself may be colored).

For each leaf \( u \), define \( c_u \) as the color of the last colored node on the simple path from the root to \( u \) (i.e. the colored node closest to \( u \)). You are given the required \( c_u \) for each leaf. Design a coloring scheme so that the total number of colored nodes is minimized while ensuring that for every leaf \( u \) the color of the last colored node on the root-to-\( u \) path is exactly \( c_u \).

Note: All formulas should be written in \( \LaTeX \) format.

inputFormat

The input begins with an integer \( m \) (\( 3 \le m \le 10^5 \)), the number of nodes in the tree.

Then follow \( m-1 \) lines, each containing two integers \( u \) and \( v \) (1-indexed), indicating an edge between nodes \( u \) and \( v \).

Finally, there is a line containing a string of length \( L \), where \( L \) is the number of leaves in the original unrooted tree (i.e. nodes whose degree is \( 1 \)). The characters of the string are either B or W. The \( i \)th character in this string is the required color \( c_u \) for the \( i \)th smallest node (by index) that is a leaf.

You may assume that the tree has at least one node with degree greater than \( 1 \) (so that a valid root exists).

outputFormat

First, output the index of the chosen root.

Then, output an integer \( k \) representing the number of nodes that are colored in your scheme.

Finally, output \( k \) lines. Each line contains an integer and a character, representing the node index and its assigned color (either B or W). The ordering of these \( k \) lines can be arbitrary.

Your output coloring must satisfy the condition that on the simple path from the root to every leaf, the last colored node has the required color, and the total number of colored nodes is minimized.

sample

3
1 2
1 3
BW

1
2
2 B
3 W