Welcome to ZOJ
Select Problem
ZOJ Problem Set - 1773
Carbon Copies

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Organic compounds are molecules mainly made up of carbon. The atoms and molecular bonds that comprise a certain organic compound molecule can be diagrammed in several ways. Two diagrams may look different but actually represent the same organic compound.

These 2 diagrams describe the same molecule (CH3CHO).

This is because they both have 2 carbon (C) atoms which have a single bond between them, and one carbon atom with a double bond with oxygen (O) and the rest of the bonds are with hydrogen (H). Without changing the atoms or breaking the molecular bonds, the atoms can be moved around so that 2 diagrams become identical.

These 2 diagrams are not equivalent, though they have the same chemical formula (C4H8).

The 1st molecule has a double bond between the 1st and 2nd carbon atoms, and the 2nd molecule has a double bond between the 2nd and 3rd carbon atoms. The atoms of the 2nd diagram cannot be moved around so that the 2 diagrams become identical.

In general, two diagrams are similar if 1.) the atoms in both can be labeled in such a way that for each pair of corresponding atoms, the 2 atoms are of the same element and 2.) they bond with the same number of other atoms of each type (element), and 3.) for each atom they bond with, they have the same type of bond.

Create a program that determines whether 2 diagrams represent the same organic compound. This program does not have to handle molecules with rings (i.e. the molecular bonds form a ring anywhere inside the molecule).


The program accepts multiple test cases. Following the last test case is a single line containing "#".

For each test case, the 1st line contains 2 numbers, A (1 <= A <= 300) and b (0 <= b <= 299), where A equals the number of atoms, and b equals the number of bonds between atoms.

The following lines contain the atomic symbols for each atom (length is 1 or 2) in the 1st molecule. Atomic symbols are entered in the normal case, i.e. upper-case 1st letter, and lower-case 2nd letter in the case of 2-letter symbols. The atoms are labeled 1, 2, 3, and so on, in the sequence they are entered. If less than A number of atoms have been read so far, read the next line until A atoms have been read.

The next b lines represent the bonds between atoms in the 1st molecule, and each line has 3 numbers separated with single spaces. The 1st number is the label of one atom (as labeled in the atom symbol sequence), and the 2nd number is the label of another atom, and the 3rd number is the type of bond (1 = single bond, 2 = double bond, 3 = triple bond).

The following line is the sequence of atomic symbols for the 2nd molecule. Again, read succeeding lines until A atoms are read. Then the last b lines represent the bonds between atoms in the 2nd molecule.

Assume that the inputs follow the laws of chemical composition, such as the Octet Rule.


For each test case, the program should output "EQUAL" if the 2 representations represent the same molecule and "NOT EQUAL" otherwise.

Sample Input

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

Sample Output


Source: Asia 2003, Manila (Philippine)
Submit    Status