Connor is taking chemistry and has gotten to the organic nomenclature unit. His teacher thinks Connor has been sleeping in class, so she decides to quiz him. She gives him an organic molecule and asks him to give some semblance of the name. Here is the naming convention this teacher's class:
- Name the branches and the carbons that they are attached by adding the number of the carbon attached and
yl. Do not repeat if there are multiple branches from a carbon.
- Name the length of longest continuous carbon chain by adding the number of carbons to the name. It is guaranteed that all carbons will be connected.
- End off the name with
Given a carbon molecule, help Connor find it's organic name!
~1 \le N \le 10^4~
~1 \le a, b \le N~
The first line of input will contain an integer ~N~, representing the number of atoms in the molecule
The next ~N - 1~ lines will contain two integers ~a~ and ~b~, representing that there is a bond between ~a~ and ~b~.
The final line of input will contain a string ~S~, which may contain the characters
O. There will be at least one
The output will contain one string ~S~, which is the name of the molecule. It should contain branches first and then carbon chain length. If there are branches on multiple nodes, output the lexicographically smallest version of ~S~, where branches from nodes that are smaller in number are put first. If there are multiple carbon chains of highest length, take the lexicographically smallest carbon chain.
Sample Input 1
5 1 2 1 3 2 4 3 5 CCCOC
Sample Output 1
Explanation for Sample 1
The graph is shown as below. Nodes ~1, 2, 3, 5~ are all carbons, whereas node ~4~ is an oxygen. This creates length ~4~ carbon chain, which represents the
4ane. There is also a branch connecting at node ~2~, which represents the
Sample Input 2
9 1 4 2 3 1 2 1 5 5 6 3 7 3 8 3 9 CCCCOOCCO
Sample Output 2
Explanation for Sample 2
There are branches at nodes ~1~ and ~3~, and the longest continuous carbon chain is length ~5~. Note that we do not put
3yl twice for the ~2~ branches at node ~3~.