package manila; import java.io.*; import java.util.*; /** * @author Tomoya Taniguchi */ public class B { static Atom[] molecule1; static Atom[] molecule2; public static boolean chk(Atom start1,int bond1,Atom start2,int bond2) { if(!start1.name.equals(start2.name))return false; if(start1.bondtype[bond1] != start2.bondtype[bond2])return false; Atom next1 = start1.bond[bond1]; Atom next2 = start2.bond[bond2]; if(!next1.name.equals(next2.name))return false; if(next1.bondNum != next2.bondNum)return false; int num = next1.bondNum; if(num <= 1) return true; boolean table[][] = new boolean[num][]; boolean[] test1 = new boolean[num]; boolean[] test2 = new boolean[num]; for(int i = 0;i < num;i++) { table[i] = new boolean[num]; } Arrays.fill(test1,false); Arrays.fill(test2,false); for(int i = 0;i < num;i++) { if(next1.bond[i] == start1) { test1[i] = true; continue; } for(int j = 0;j < num;j++) { if(next2.bond[j] == start2) { test2[j] = true; continue; } table[i][j] = chk(next1,i,next2,j); } } return chk2(test1,test2,table,num); } static boolean chk2(boolean[] test1,boolean[] test2,boolean[][] table,int num) { boolean chk = true; for(int i = 0;i < num;i++) { chk = chk && test1[i] && test2[i]; } if(chk) { return true; } for(int i = 0;i < num;i++) { if(test1[i])continue; for(int j = 0;j < num;j++) { if(test2[j])continue; if(table[i][j]) { test1[i] = true; test2[j] = true; boolean b = chk2(test1,test2,table,num); if(b)return true; test1[i] = false; test2[j] = false; } } } return false; } static void chk2test()//for debug { int num = 3; boolean[] a = new boolean[]{false,false,false}; boolean[] b = new boolean[]{false,false,false}; boolean[][] table = new boolean[][]{ new boolean[]{true,false,false}, new boolean[]{false,true,false}, new boolean[]{false,true,false} }; System.out.println(chk2(a,b,table,num)); } public static void main(String[] args)throws Exception { //chk2test(); BufferedReader r = new BufferedReader(new FileReader("carbon.in")); while(true) { String str = r.readLine(); if("#".equals(str))break; StringTokenizer st = new StringTokenizer(str); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); molecule1 = new Atom[a]; molecule2 = new Atom[a]; st = new StringTokenizer(r.readLine()); for(int i = 0;i < a;i++) { if(!st.hasMoreTokens()) st = new StringTokenizer(r.readLine()); molecule1[i] = new Atom(st.nextToken()); } for(int i = 0;i < b;i++) { st = new StringTokenizer(r.readLine()); int first = Integer.parseInt(st.nextToken()); int second = Integer.parseInt(st.nextToken()); int type = Integer.parseInt(st.nextToken()); molecule1[first-1].addBond(molecule1[second-1],type); molecule1[second-1].addBond(molecule1[first-1],type); } st = new StringTokenizer(r.readLine()); for(int i = 0;i < a;i++) { if(!st.hasMoreTokens()) st = new StringTokenizer(r.readLine()); molecule2[i] = new Atom(st.nextToken()); } for(int i = 0;i < b;i++) { st = new StringTokenizer(r.readLine()); int first = Integer.parseInt(st.nextToken()); int second = Integer.parseInt(st.nextToken()); int type = Integer.parseInt(st.nextToken()); molecule2[first-1].addBond(molecule2[second-1],type); molecule2[second-1].addBond(molecule2[first-1],type); } boolean flag = false; if(a == 1) { flag = molecule1[0].name.equals(molecule2[0].name); } if(!flag) for(int i = 0;i < a;i++) { if(molecule1[i].bondNum == 1) for(int j = 0;j < a;j++) { if(molecule2[j].bondNum == 1) { flag = chk(molecule1[i],0,molecule2[j],0); if(flag)break; } } if(flag)break; } if(flag) System.out.println("EQUAL"); else System.out.println("NOT EQUAL"); } } } class Atom { public int bondNum; public Atom[] bond; public int[] bondtype; public String name; public Atom(String name) { bond = new Atom[300]; bondtype = new int[300]; bondNum = 0; this.name = name; } public void addBond(Atom atom,int type) { this.bondtype[bondNum] = type; this.bond[bondNum++] = atom; } }