Equivalent Strings

Time limit1sMemory limit1024 MB

Summary

Given pairs of commuting letters, decide whether string t can be reached from s by swapping adjacent commuting letters.

Level: Medium6 of 10
Topics: String, Implementation
Solved: No attempts yet

Problem

Consider strings made of the first $k$ letters of the English alphabet. Some pairs of letters are called commuting. If two commuting letters stand next to each other in a string, they may be swapped.

You are given the commuting pairs and two strings $s$ and $t$ of equal length. Determine whether $t$ can be obtained from $s$ by performing any number of operations, where each operation swaps two adjacent commuting letters.

Input

The first line contains two integers $k$ and $n$ , the number of letters used and the number of commuting pairs ( $2 \le k \le 10$ , $0 \le n \le k(k-1)/2$ ).

Each of the next $n$ lines contains two letters with no space between them, forming a commuting pair. Each pair appears at most once.

The next two lines contain the strings $s$ and $t$ . They have the same length $L$ ( $1 \le L \le 100\,000$ ) and consist of the first $k$ letters of the Latin alphabet.

Output

Print YES if $t$ can be obtained from $s$ using the described operations. Otherwise, print NO.

Examples2

Example 1
Input
```
3 2
ab
bc
abbcabc
abcacbb
```
Expected output
```
YES
```
Example 2
Input
```
3 2
ab
bc
abbcabc
aabbbcc
```
Expected output
```
NO
```