A15053. Evolution of Weasels
编程题
普及/提高-
知识点
题目描述
A wild basilisk just appeared at your doorstep. You are not entirely sure what a basilisk is and you wonder whether it evolved from your favorite animal, the weasel.
How can you find out whether basilisks evolved from weasels? Certainly, a good first step is to sequence both of their DNAs. Then you can try to check whether there is a sequence of possible mutations from the DNA of the weasel to the DNA of the basilisk.
Your friend Ron is a talented alchemist and has studied DNA sequences in many of his experiments. He has found out that DNA strings consist of the letters A, B and C and that single mutations can only remove or add substrings at any position in the string (a substring is a contiguous sequence of characters). The substrings that can be removed or added by a mutation are AA, BB, CC, ABAB or BCBC. During a sequence of mutations a DNA string may even become empty.
Ron has agreed to sequence the DNA of the weasel and the basilisk for you, but finding out whether there is a sequence of possible mutations that leads from one to the other is too difficult for him, so you have to do it on your own.
How can you find out whether basilisks evolved from weasels? Certainly, a good first step is to sequence both of their DNAs. Then you can try to check whether there is a sequence of possible mutations from the DNA of the weasel to the DNA of the basilisk.
Your friend Ron is a talented alchemist and has studied DNA sequences in many of his experiments. He has found out that DNA strings consist of the letters A, B and C and that single mutations can only remove or add substrings at any position in the string (a substring is a contiguous sequence of characters). The substrings that can be removed or added by a mutation are AA, BB, CC, ABAB or BCBC. During a sequence of mutations a DNA string may even become empty.
Ron has agreed to sequence the DNA of the weasel and the basilisk for you, but finding out whether there is a sequence of possible mutations that leads from one to the other is too difficult for him, so you have to do it on your own.
输入格式
Each test contains multiple test cases. The first line contains an integer $t$ ( $1\le t\le 100$ ) — the number of test cases. The descriptions of the $t$ test cases follow.
The first line of each test case contains a string $u$ ( $1\le |u|\le 200$ ) — the DNA of the weasel.
The second line of each test case contains a string $v$ ( $1\le |v|\le 200$ ) — the DNA of the basilisk.
The values $|u|$ , $|v|$ denote the lengths of the strings $u$ and $v$ . It is guaranteed that both strings $u$ and $v$ consist of the letters A, B and C.
The first line of each test case contains a string $u$ ( $1\le |u|\le 200$ ) — the DNA of the weasel.
The second line of each test case contains a string $v$ ( $1\le |v|\le 200$ ) — the DNA of the basilisk.
The values $|u|$ , $|v|$ denote the lengths of the strings $u$ and $v$ . It is guaranteed that both strings $u$ and $v$ consist of the letters A, B and C.
输出格式
For each test case, print YES if there is a sequence of mutations to get from $u$ to $v$ and NO otherwise.
输入输出样例
输入 #1
8 A B B C C A AA BB BB CC CC AA ABAB BCBC ABC CBA
输出 #1
NO NO NO YES YES YES YES NO