CSES - E4590 2017 1 - 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

  • 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