Consider strings consisting of the first k letters of the English alphabet. Some pairs of letters are called commuting: if they are adjacent in a line, they are allowed to swap.
Given pairs of commuting letters and two strings of equal length s and t. It is required to find out whether it is possible to get t from s by performing an arbitrary number of operations: swap two adjacent commuting letters.
Input
The first line contains two integers k and n — the number of letters used and the number of pairs of switching letters (2 ≤ k ≤ 10, 0 ≤ n ≤ k(k − 1)/2).
The next n lines contain two letters each, not separated by spaces: pairs of commuting letters. It is guaranteed that each pair is given at most once in the input.
The next two lines contain the strings s and t, they are equal in length L (1 ≤ L ≤ 100 000) and consist of the first k letters of the Latin alphabet.
Imprint
Print "YES" if the string t can be obtained from the string s by the described operations.
Otherwise print "NO".
Examples
| # |
Input |
Output |
| 1 |
3 2
ab
bc
abbcabc
abcacbb |
YES |
| 2 |
3 2
ab
bc
abbcabc
aabbbcc |
NO |