Organic Nomenclature

View as PDF

Points: 7
Time limit: 1.0s
Memory limit: 64M

Authors:
Problem type

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 ane.

Given a carbon molecule, help Connor find it's organic name!

Input Specification

The first line of input will contain an integer , representing the number of atoms in the molecule

The next lines will contain two integers and , representing that there is a bond between and .

The final line of input will contain a string , which may contain the characters C and O. There will be at least one C.

Output Specification

The output will contain one string , 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 , 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

2yl4ane

Explanation for Sample 1

The graph is shown as below. Nodes are all carbons, whereas node is an oxygen. This creates length carbon chain, which represents the 4ane. There is also a branch connecting at node , which represents the 2yl.

Sample Input 2

9
1 4
2 3
1 2
1 5
5 6
3 7
3 8
3 9
CCCCOOCCO

Sample Output 2

1yl3yl5ane

Explanation for Sample 2

There are branches at nodes and , and the longest continuous carbon chain is length . Note that we do not put 3yl twice for the branches at node .

Comments

There are no comments at the moment.