给你两个长度相等的字符串 $$$a$$$ 和 $$$b$$$,仅包含字符 0 和/或 1;两个字符串都以字符 0 开头并以字符 1 结尾。
您可以执行以下操作任意次数(可能为零):
- 选择字符串之一和其中两个相等的字符;然后将它们之间的所有字符都转换为这些字符。
正式地,您选择这两个字符串之一(让所选字符串为 $$$s$$$),然后选择两个整数 $$$l$$$ 和 $$$r$$$ 使得 $$$1 \le l < r \le |s|$$$ 和 $$$s_l = s_r$$$,然后替换每个字符 $$$s_i$$$ 使得 $$$l < i < r$$$与$$$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
7 01010001 01110101 01001 01001 000101 010111 00001 01111 011 001 001001 011011 010001 011011
输出 #1
YES YES YES NO NO NO YES
注意
在第一个测试用例中,我们可以执行以下操作:
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;
在第四个和第五个测试用例中,不可能使给定的字符串相等。