Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3830

Time Limit: 2 Seconds      Memory Limit: 65536 KB

The IUPAC nomenclature of organic chemistry is a systematic method of naming organic chemical compounds as recommended by the International Union of Pure and Applied Chemistry (IUPAC). Here are the rules for alkanes (except cyclic alkanes).

Straight-chain alkanes take the suffix "-ane" and are prefixed depending on the number of carbon atoms in the chain, following standard rules. The first few are:

Number of carbons 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
prefix meth eth prop but pent hex hept oct non dec undec dodec tridec tetradec pentadec

For example, the simplest alkane is CH4 methane, and the nine-carbon alkane CH3(CH2)7CH3 is named nonane.


Branched alkanes are named as a straight-chain alkane with attached side chains (alkyl groups). Name each side chain by changing the suffix of the name of the alkane from "-ane" to "-yl". They are prefixed with a number indicating the carbon the group is attached to, counting from the end of the alkane chain. For example, (CH3)2CHCH3, is treated as a propane chain with a methyl group bonded to the middle (2) carbon, and given the systematic name 2-methylpropane.

If there is ambiguity in the position of the substituent, number the root chain so that sum of the numbers assigned to each side group will be as low as possible. For example, (CH3)2CHCH2CH3 is named 2-methylbutane, not 3-methylbutane.


If there are multiple side-branches of the same size alkyl group, their positions are separated by commas in ascending order and the group prefixed with 'di'(2), 'tri'(3), 'tetra'(4), etc.(as for 5 ~ 15, you can refer to the table above and add 'a' at last, such as 'penta'(5), 'hexa'(6), etc), depending on the number of branches (e.g. C(CH3)4 2,2-dimethylpropane). If there are different groups, they are added in alphabetical order, separated by commas or hyphens: 3-ethyl-4-methylhexane. The longest possible main alkane chain is used; therefore 3-ethyl-4-methylhexane instead of 2,3-diethylpentane, even though these describe equivalent structures. The di-, tri- etc. prefixes are ignored for the purpose of alphabetical ordering of side chains (e.g. 3-ethyl-2,4-dimethylpentane, not 2,4-dimethyl-3-ethylpentane).


There will be multiple cases.

For each cases, there are two numbers in the first line: n and m. n is the number of carbon atoms, and m is the number of carbon bond (witch is always equal to n-1).

There are m lines follow, indicating the identify numbers of two carbon atoms linked together. The identify numbers of the carbon atoms varies for 1 to n.

The main straight-chain of the alkane is no longer than 15, each side chain is no longer than 15, and the number of side chains with the same size is no larger than 15. Anyhow, the original IUPAC nomenclature is much more complicated, this problem states only a subset of the IUPAC nomenclature. You can assume all the test cases can be solved by the rules in the statement.


Output the name of alkanes using IUPAC nomenclature.

Sample Input

5 4
1 2
2 3
2 5
2 4

4 3
1 2
2 3
3 4

13 12
1 2
2 3
3 4
4 5
5 6
6 7
7 8
9 10
10 11
11 12
12 13
12 4

Sample Output



For the last sample, the graph looks like that:


Author: LIN, Tao
Source: ZOJ Monthly, November 2014
Submit    Status