题目描述

给定两个长度相等、仅由字符 $0$ 和 $1$ 组成的字符串 $a$ 和 $b$，且这两个字符串都以字符 $0$ 开头，以字符 $1$ 结尾。

你可以对任意一个字符串进行如下操作任意次（也可以不操作）：

• 选择其中一个字符串和其中两个相同的字符，然后将这两个字符之间的所有字符都变成这两个字符的值。

形式化地说，你选择两个整数 $l$ 和 $r$，满足 $1 \le l < r \le |s|$ 且 $s_l = s_r$，然后将所有满足 $l < i < r$ 的 $s_i$ 替换为 $s_l$。

例如，如果当前字符串为 010101，你可以通过一次操作将其变为以下任意一种：

• 000101，若选择 $l = 1$，$r = 3$；
• 000001，若选择 $l = 1$，$r = 5$；
• 010001，若选择 $l = 3$，$r = 5$；
• 010111，若选择 $l = 4$，$r = 6$；
• 011111，若选择 $l = 2$，$r = 6$；
• 011101，若选择 $l = 2$，$r = 4$。

你需要判断，是否可以通过若干次上述操作，使得两个字符串变得完全相同。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 2000$），表示测试用例的数量。

每个测试用例包含两行：

• 第一行是字符串 $a$（$2 \le |a| \le 5000$），仅包含字符 $0$ 和 $1$。
• 第二行是字符串 $b$（$2 \le |b| \le 5000$），仅包含字符 $0$ 和 $1$。

输入的额外约束：

• 每个测试用例中，$|a| = |b|$（两个字符串长度相等）；
• 每个测试用例中，两个字符串都以 $0$ 开头，以 $1$ 结尾；
• 所有测试用例中，所有字符串 $a$ 的总长度不超过 $5000$。

输出格式

对于每个测试用例，如果可以通过若干次操作使得两个字符串相等，输出 YES；否则输出 NO。你可以用任意大小写输出答案。

说明/提示

在第一个测试用例中，可以进行如下操作：

1. 选择字符串 $a$，$l = 2$，$r = 4$；操作后，$a$ 变为 01110001，$b$ 变为 01110101；
2. 选择字符串 $b$，$l = 5$，$r = 7$；操作后，$a$ 变为 01110001，$b$ 变为 01110001。

在第二个测试用例中，两个字符串已经相等。

在第三个测试用例中，可以进行如下操作：

1. 选择字符串 $a$，$l = 4$，$r = 6$；操作后，$a$ 变为 000111，$b$ 变为 010111；
2. 选择字符串 $b$，$l = 1$，$r = 3$；操作后，$a$ 变为 000111，$b$ 变为 000111。

在第四和第五个测试用例中，不可能使两个字符串相等。

由 ChatGPT 4.1 翻译

样例

7
01010001
01110101
01001
01001
000101
010111
00001
01111
011
001
001001
011011
010001
011011

YES
YES
YES
NO
NO
NO
YES