Palindrome Rearrangement with Friend Pairs

You are given a string s and a list of friend pairs. Two letters that are friends can be considered identical when forming a palindrome. Determine if it is possible to rearrange the string into a palindrome by treating friends as equivalent characters.

Formally, let each friend pair (a, b) indicate that letter a is equivalent to letter b. Using union-find (disjoint set union) structure, merge the letters. Then, count the frequency of each group representative in the string. A palindrome can be formed if at most one group's frequency is odd.

The input is provided via standard input, and the output should be written to standard output.

inputFormat

The first line contains a non-empty string s consisting of lowercase English letters.

The second line contains an integer n representing the number of friend pairs.

The next n lines each contain two space-separated lowercase letters representing a friend pair.

outputFormat

Output a single line containing YES if it is possible to rearrange the string into a palindrome considering the friend relationships, otherwise output NO.

## sample

abac
2
a b
a c

YES

</p>