Two Binary Strings
Contest: Educational Codeforces Round 154 (Rated for Div. 2)
Difficulty rating: 1000
Tags: constructive algorithms, dp, greedy

You are given two strings $$$a$$$ and $$$b$$$ of equal length, consisting of only characters 0 and/or 1; both strings start with character 0 and end with character 1.

You can perform the following operation any number of times (possibly zero):

- choose one of the strings and two equal characters in it; then turn all characters between them into those characters.

Formally, you choose one of these two strings (let the chosen string be $$$s$$$), then pick two integers $$$l$$$ and $$$r$$$ such that $$$1 \le l < r \le |s|$$$ and $$$s_l = s_r$$$, then replace every character $$$s_i$$$ such that $$$l < i < r$$$ with $$$s_l$$$.

For example, if the chosen string is 010101, you can transform it into one of the following strings by applying one operation:

- 000101 if you choose $$$l = 1$$$ and $$$r = 3$$$;
- 000001 if you choose $$$l = 1$$$ and $$$r = 5$$$;
- 010001 if you choose $$$l = 3$$$ and $$$r = 5$$$;
- 010111 if you choose $$$l = 4$$$ and $$$r = 6$$$;
- 011111 if you choose $$$l = 2$$$ and $$$r = 6$$$;
- 011101 if you choose $$$l = 2$$$ and $$$r = 4$$$.

You have to determine if it's possible to make the given strings equal by applying this operation any number of times.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2000$$$)  — the number of test cases.

Each test case consists of two lines:

- the first line contains the string $$$a$$$ ($$$2 \le |a| \le 5000$$$), consisting of only characters 0 and/or 1.
- the second line contains the string $$$b$$$ ($$$2 \le |b| \le 5000$$$), consisting of only characters 0 and/or 1.

Additional constraints on the input:

- in each test case, $$$|a| = |b|$$$ (the strings have equal length);
- in each test case, both strings start with 0 and end with 1;
- the total length of all strings $$$a$$$ in all test cases does not exceed $$$5000$$$.

Output format:
For each test case, print YES if it is possible to make the strings equal. Otherwise, print NO. You can print each letter in any register.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we can perform the following operations:

1. choose the string $$$a$$$, $$$l = 2$$$, $$$r = 4$$$; after this operation, $$$a$$$ is 01110001, $$$b$$$ is 01110101;
2. choose the string $$$b$$$, $$$l = 5$$$, $$$r = 7$$$; after this operation, $$$a$$$ is 01110001, $$$b$$$ is 01110001.

In the second test case, the strings are already equal.

In the third test case, we can perform the following operations:

1. choose the string $$$a$$$, $$$l = 4$$$, $$$r = 6$$$; after this operation, $$$a$$$ is 000111, $$$b$$$ is 010111;
2. choose the string $$$b$$$, $$$l = 1$$$, $$$r = 3$$$; after this operation, $$$a$$$ is 000111, $$$b$$$ is 000111;

In the fourth and fifth test cases, it's impossible to make the given strings equal.

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

Example output:
YES
YES
YES
NO
NO
NO
YES

Editorial:
If the answer is YES, we can always bring both strings to the form $$$00 \dots 01 \dots 11$$$ (some prefix consists of zeros, some suffix consists of ones, and all zeroes are before all ones). It's true because after we make both strings equal, we can apply another operation with $$$l = i, r = |a|$$$, where $$$i$$$ is the minimum index where both strings have $$$1$$$ after we made them equal. For example, in the first test case, the strings are equal to $$$01110001$$$ after applying all operations considered in the statement. We can turn them into the string $$$01111111$$$ by applying operation with $$$l = 2, r = 8$$$.
Okay, now let's try to find out when we can transform a string into the form $$$00 \dots 0011 \dots 11$$$. We claim that it's possible to transform the string $$$s$$$ into the form "$$$i$$$ first elements are zeroes, all the remaining elements are ones" if and only if $$$s_i = 0$$$ and $$$s_{i+1} = 1$$$:
• if $$$s_i = 0$$$ and $$$s_{i+1} = 1$$$, we can apply two operations with $$$l = 1, r = i$$$ and $$$l = i+1, r = |s|$$$, and the string turns into the form "$$$i$$$ first elements are zeroes, all the remaining elements are ones";
• however, if that's not the case, then either $$$s_i = s_{i+1}$$$, or $$$s_i = 1$$$ and $$$s_{i+1} = 0$$$. In the former case, we need to change one of these two elements; but since they are equal and adjacent, every operation on them will affect them both, so it's impossible to change only one of them. In the latter case, we need to set either $$$s_i$$$ to $$$0$$$ or $$$s_{i+1}$$$ to $$$1$$$ first; and when we do it, the elements become equal, and every operation on them will affect them both. So, it's impossible to bring the string into the form "$$$i$$$ first elements are zeroes, all the remaining elements are ones".
So, the answer is YES if there is an index $$$i$$$ such that $$$a_i = b_i = 0$$$ and $$$a_{i+1} = b_{i+1} = 1$$$. Otherwise, the answer is NO.