In this challenge, the set of translations forms a directed graph on the $26$ letters of the alphabet. You are given two query words s$1$s$2$s$3...$sL and t$1$t$2$t$3...$tL of equal length L$.$ You need to check whether for each $1<=$i$<=$L$,$ there is a path from si to ti in the graph of letter translations. Keep in mind, that if the lengths are different, the answer is definately $"$no$".$

An easy way of doing this is to precompute the transitive closure of the graph using the Floyd$-$Warshall algorithm. This algorithm allows to check each pair $($si$,$ ti$)$ in constant time. Since the bounds are small, you may use any polynomial time algorithm.

You probably know that there is a spectacular stone sculpture featuring four famous U$.$S$.$ presidents at Mount Rushmore and this monument contains a secret chamber. It can be found behind the head of Abraham Lincoln and was designed to serve as a Hall of Records to store important historical U$.$S$.$ documents and artifacts. Historians claim that the construction of the hall was halted in $1939$ and the uncompleted chamber was left untouched until the late $1990$s$,$ but this is not the whole truth.

In $1982,$ an archaeologist secretly visited the monument and found that the chamber actually was completed, but it was kept confidential. This seemed suspicious and after some poking around, she found a hidden vault and some documents inside. Unfortunately, these documents did not make any sense. She suspected that they had been written in a code, but she could not decipher them despite all her efforts. Earlier this week she discovered the key to a document that contains a list of translations of letters. Some letters may have more than one translation, and others may have no translation.

By repeatedly applying some of these translations to individual letters in the gibberish documents, she might be able to decipher them to yield historical U$.$S$.$ documents. She needs your help. You are given the possible translations of letters and a list of pairs of original and deciphered words. Your task is to verify whether the words in each pair match. Two words match if they have the same length and if each letter of the first word can be turned into the corresponding letter of the second word by using the available translations zero or more times. Check the attached document for a hint on input and output values with a sample provided on both.