You will be given a string of characters between ‘a’ to ‘j’ and a list of M pair of characters, u and v. You can perform the following operation.

First you have to choose a pair of characters, u and v from the given list. Then, you can replace a character u in the given string with v. After the replacement the new string will be your given string.

You have to output whether you can rearrange the characters in the given string in non-decreasing order by performing this operation any number of times.

INPUT: First line contains an integer T denotes the number of test cases. Each test case starts with a string of length N. Following line contains an integer M denotes the number of pairs of characters. Each of the following M lines contain two characters u and v. Here, 1 ≤ T ≤ 100, 1 ≤ N ≤ 10000, 0 ≤ M ≤ 500, ‘a’ ≤ u, v ≤ ‘j’.

OUTPUT: For each test case, you have to print ‘YES’ (without quotes) if the given string can be rearranged in non-decreasing order, otherwise print ‘NO’.

SAMPLE INPUT:

3

adb

0

abed

2

d a

e d

abed

2

d a

d g

SAMPLE OUTPUT:

NO

YES

YES