Organic Nomenclature

View as PDF

Submit solution

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

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!


1 \le N \le 10^4

1 \le a, b \le N

Input Specification

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 C and O. There will be at least one C.

Output Specification

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

1 2
1 3
2 4
3 5

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 2yl.

Sample Input 2

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

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.


There are no comments at the moment.