← 返回题目列表

Codeforces · 1662/D

D. 黄鼠狼的进化

中文机器翻译题面 查看原题

一只野生蛇怪刚刚出现在你家门口。您并不完全确定蛇怪是什么,您想知道它是否是从您最喜欢的动物黄鼠狼进化而来的。

如何判断蛇怪是否是由黄鼠狼进化而来?当然,好的第一步是对他们的 DNA 进行测序。然后你可以尝试检查从黄鼠狼的DNA到蛇怪的DNA是否存在可能的突变序列。

你的朋友 Ron 是一位才华横溢的炼金术士,在他的许多实验中研究了 DNA 序列。他发现 DNA 字符串由字母 A、B 和 C 组成,并且单个突变只能在字符串中的任何位置删除或添加子字符串(子字符串是连续的字符序列)。可以通过突变删除或添加的子字符串是 AA、BB、CC、ABAB 或 BCBC。在一系列突变过程中,DNA 串甚至可能变空。

罗恩同意为你对黄鼠狼和蛇怪的 DNA 进行测序,但找出是否存在从一个到另一个的可能突变序列对他来说太困难了,所以你必须自己做。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 100$$$) — 测试用例的数量。 $$$t$$$ 测试用例的描述如下。

每个测试用例的第一行包含一个字符串 $$$u$$$ ($$$1\le |u|\le 200$$$) — 黄鼠狼的 DNA。

每个测试用例的第二行包含一个字符串 $$$v$$$ ($$$1\le |v|\le 200$$$) — 蛇怪的 DNA。

值 $$$|u|$$$、$$$|v|$$$ 表示字符串 $$$u$$$ 和 $$$v$$$ 的长度。保证字符串 $$$u$$$ 和 $$$v$$$ 均由字母 A、B 和 C 组成。

输出

对于每个测试用例,如果存在从 $$$u$$$ 到 $$$v$$$ 的突变序列,则打印 YES,否则打印 NO。

示例

输入 #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