Code Submission Evaluation System Login

E4590 2018 1

Start:2018-09-15 13:00:00
End:2018-09-15 16:00:00
 

Tasks | Scoreboard | Statistics


CSES - E4590 2018 1 - Swapping lettersCSES - Swapping letters

Swapping letters

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
Example 1

Input:
2
a b
b c
acbbaca
cabbaac


Output:
YES

Example 2

Input:
2
a b
b c
acbbaca
baccaab


Output:
NO