- Time limit: 1.00 s
- Memory limit: 512 MB
Not all pairs of letters are equal!
You are given two strings, x and y, and your task is to turn string x into string y by swapping pairs of letters that are next to each other. For example, you can turn x={}"acbbaca" into y={}"baccaab" as follows:
acbbaca abcbaca bacbaca bacbcaa baccbaa baccaba baccaab
However, this time we have an extra restriction: you get a list of pairs that cannot be swapped. These are called forbidden pairs. For example, if (a,b) is a forbidden pair, then it means that you cannot replace "ab" with "ba", and you cannot replace "ba" with "ab".
If, for example, we had forbidden pairs (a,b) and (b,c), then it would not be possible to turn "acbbaca" into "baccaab". No matter how you try to do it, you would need to replace "ab" with "ba", or "ba with "ab", or "bc" with "cb", or "cb" with "bc".
In this problem, you are given the strings x and y and n forbidden pairs, and your task is to tell if you can get from x to y by swapping adjacent characters and avoiding all forbidden pairs.
Input
The first line contains a number n.
Then there are n rows of forbidden pairs. Each row contains two characters, u and v, separated with a space. This means that you are not permitted to replace the substring uv with vu or vice versa. We will always have u \ne v.
Finally there are two lines that contain the strings x and y.
All strings consist of lower-case letters "a"–"z" only.
Output
Output "YES", if you can get from x to y avoiding forbidden pairs; otherwise output "NO".
Limits
- 0 \le n \le 325
- The length of strings x and y is between 1 and 10^6 characters.
Example 1
Input:
2 a b b c acbbaca cabbaac
Output:
YES
Example 2
Input:
2 a b b c acbbaca baccaab
Output:
NO