Decrypt the Encrypted Message

You are given an encrypted message t and m transformation rules. Each rule is a pair \((a, b)\) in \(\LaTeX\) format, meaning that the encrypted character b can be transformed back to its original character a. Your task is to determine if it is possible to decrypt the entire message by reversing the transformations.

For each character in the encrypted message, you must determine if there is a sequence of transformations (possibly via intermediate steps) that leads to a character which originally appears as the first element in any rule.

Hint: Think of the transformation rules as a directed graph where an edge from \(b\) to \(a\) exists if the rule \((a, b)\) is given. Then, for each character in the encrypted message, perform a search (e.g., a breadth-first search) on this graph to see if you can reach any original character.

inputFormat

The input is given via standard input (stdin) in the following format:

• The first line contains the encrypted message string t.
• The second line contains an integer m, representing the number of transformation rules.
• The next m lines each contain two space-separated characters. The first character of each line is the original character and the second is the encrypted character.

outputFormat

Output a single line to standard output (stdout): YES if every character in the encrypted message t can be transformed back to an original character by following the transformation rules; otherwise, output NO.

hello
3
h e
e l
l o

YES